ARC181D Prefix Bubble Sort

传送门

Solution

先用树状数组求逆序对，得出数组总共的逆序对数量 $tot$。设 $a_i$ 和它前面的数共组成 $inv_i$ 对逆序对。

手玩样例后不难理解，操作 $i$ 的本质，其实就是对所有 $j\le i$，若 $a_j$ 非零，则 $a_j-1$。设执行操作 $i$ 前有 $m$ 个 $a_j$ 非零，则执行操作后整个序列的逆序对数量减少 $m$。

由于操作保证升序，所以每次操作都可以把新的非零 $a_j$ 放入优先队列，并将优先队列里的元素全部减一。当然，只用新建一个变量 $flg$ $O(1)$ 记录减的值即可。若计算得出队头为零，则弹出。$m$ 即为优先队列的规模。$tot-m$ 为当前答案。

每个 $a_i$ 最多入队出队各一次，时间复杂度为 $O(n\log n)$。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll N = 1e6 + 10;

ll n, a[N], q, sum[N], tr[N], ans, flg;
priority_queue<ll, vector<ll>, greater<ll> > que;

ll lowbit(ll x) {return x & -x;}

void add(ll x, ll c)
{
	for (; x <= n; x += lowbit(x))
		tr[x] += c;
}

ll query(ll x)
{
	ll res = 0;
	for (; x > 0; x -= lowbit(x))
		res += tr[x];
	return res; 
}

int main()
{
	scanf("%lld", &n);
	for (ll i = 1; i <= n; i++)
		scanf("%lld", &a[i]);
	scanf("%lld", &q);
	ll p = 1;
	for (ll i = 1; i <= n; i++) {
		sum[i] = i - query(a[i]) - 1;
		ans += sum[i];
		add(a[i], 1);
	}
	while (q--) {
		++flg;
		ll x;
		scanf("%lld", &x);
		while (p <= x) {
			if (sum[p] + flg - 1 > 0 && sum[p])
				que.push(sum[p] + flg - 1);
			++p;
		}
		ans -= que.size();
		while (que.size() && que.top() <= flg)
			que.pop();
		
		printf("%lld\n", ans);
	}
	return 0;
}