【题解】CF1830E Bully Sort

考虑一次交换，我们发现，被选出来的 \([i,j]\) 的区间里 \(p_i\) 一定是最大的，\(p_j\) 一定是最小的。

然后我们会发现，我们原序列的逆序对数量会减少 \(2(j-i) - 1\)，而 \(\sum|p_i-i|\) 会减少 \(2(j-i)\)

那么答案就是原序列的两部分相减（神奇的性质又增加了！）。

至于我们的后半部分显然是很好维护的，而逆序对数量只需要使用三位偏序求解即可。

yes，搞定！

code:

#include<bits/stdc++.h>
using namespace std;
const int NN = 5e5 + 8;
typedef long long ll;
int n,m,tot;
int p[NN];
ll res[NN];
ll ans[NN];
struct Node{
	int t,x,y,val;
	bool operator < (const Node &A){
		return x < A.x;
	}
}q[NN << 1],Q[NN << 1];
int a[NN];
inline lowbit(int x){return x & (-x);}
void add(int x,int num){
	while(x <= n){
		a[x] += num;
		x += lowbit(x);
	}
}
int ask(int x){
	int res = 0;
	while(x > 0){
		res += a[x];
		x -= lowbit(x);
	}
	return res;
}
void solve(int l,int r){
	if(l == r) return;
	int mid = (l + r) / 2;
	solve(l,mid);solve(mid+1,r);
	
	int i = l,j = mid + 1,k = l;
	while(i <= mid && j <= r){
		if(q[i].x <= q[j].x) add(q[i].y,q[i].val),Q[k++] = q[i++];
        else ans[q[j].t] += (ask(n) - ask(q[j].y)) * q[j].val,Q[k++] = q[j++];
	}
	while(i <= mid) add(q[i].y,q[i].val),Q[k++] = q[i++];
	while(j <= r) ans[q[j].t] += (ask(n) - ask(q[j].y)) * q[j].val,Q[k++] = q[j++];
	for(int i = l; i <= mid; ++i) add(q[i].y,-q[i].val);
	
	i = mid,j = r;
	while(i >= l && j > mid){
		if(q[i].x >= q[j].x) add(q[i].y,q[i].val),--i;
        else ans[q[j].t] += ask(q[j].y-1) * q[j].val,--j;
	}
	while(i >= l) add(q[i].y,q[i].val),--i;
	while(j > mid) ans[q[j].t] += ask(q[j].y-1) * q[j].val,--j;
	for(int i = l; i <= mid; ++i) add(q[i].y,-q[i].val);
	
	for(int i = l; i <= r; ++i) q[i] = Q[i];
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= n; ++i){
		scanf("%d",&p[i]);
		q[++tot] = {0,i,p[i],1};
		res[0] += abs(p[i] - i);
	}
	for(int i = 1,x,y; i <= m; ++i){
		scanf("%d%d",&x,&y);
		res[i] = res[i-1];
		res[i] -= abs(p[x]-x) + abs(p[y]-y);
		q[++tot] = {i,x,p[x],-1}, q[++tot] = {i,y,p[y],-1};
        swap(p[x],p[y]);
        res[i] += abs(p[x]-x) + abs(p[y]-y);
        q[++tot]={i,x,p[x],1},q[++tot]={i,y,p[y],1};
	}
	solve(1,tot);
	for(int i = 1; i <= m; ++i){
        ans[i] += ans[i-1];
        printf("%lld\n",res[i] - ans[i]);
    }
}