题目大意

给定一个长为 $n$ 的排列 $p$，有如下操作

  • 交换 $p_{x}, p_{x+1}$。
  • 询问排列经过 $k$ 轮冒泡排序后的逆序数。

分析

难点在观察冒泡排序对逆序数的影响，考虑一个数 $p_i$ 受其前面的数影响：

  • 如果 $p_i$ 前面没有比 $p_i$ 大的，冒泡后 $p_{i’}$ 仍不贡献逆序数。
  • 如果 $p_i$ 前面有 $j$ 个比当前数大的，冒泡后有且仅有一个数穿过了 $p_{i’}$，贡献的逆序数减 $1$。

故第 $k$ 轮冒泡后，即每个数贡献的逆序数都要减 $k$。又因为不应减到负数，因此需要用两个树状数组维护。

#include "template/ds/fwtree/1.hpp"

int main() {
	int n = rr(), m = rr();
	vector<int> p(n);
	for (int i = 0; i < n; i++)
		p[i] = rr();

	vector<ll> inver(n);
	{
		vector<pii> tp(n);
		for (int i = 0; i < n; i++)
			tp[i] = {p[i], i + 1};
		sort(tp.begin(), tp.end());
		fwtree_1<ll> tr(n + 1);
		for (auto [x, i] : tp) {
			inver[i - 1] = i - 1 - tr.sum(1, i);
			tr.add(i, 1);
		}
	}
	fwtree_1<ll> tr1(n + 1), tr2(n + 1);
	for (auto ii : inver) {
		tr1.add(ii, 1), tr2.add(ii, ii);
	}
	
	while (m--) {
		int op = rr();
		if (op == 1) {
			int x = rr() - 1;
			swap(p[x], p[x + 1]);
			swap(inver[x], inver[x + 1]);
			if (p[x] < p[x + 1]) {
				auto &ii = inver[x];
				tr1.add(ii, -1);
				tr2.add(ii, -ii);
				ii--;
				tr1.add(ii, 1);
				tr2.add(ii, ii);
			} else {
				auto &ii = inver[x + 1];
				tr1.add(ii, -1);
				tr2.add(ii, -ii);
				ii++;
				tr1.add(ii, 1);
				tr2.add(ii, ii);
			}
		} else {
			ll k = rr();
			if (k > n) {
				printf("0\n");
			} else {
				ll ans = tr2.sum(k, n);
				ans -= tr1.sum(k, n) * k;
				printf("%lld\n", ans);
			}
		}
	}
	return 0;
}