Codeforces 1830E - Bully Sort

这种题肯定首先要寻找不变量。

显然后面排好序的后缀不会被改变。因此从整体上来看我们的流程肯定是，如果当前 \(p_n=n\)，就令 \(n\) 减一，否则你一步换的 \(i\) 肯定满足 \(p_i=n\)。而显然 \(\min\limits_{j=i}^np_j\le i\)，因此我们考察 \(\sum|i-p_i|\) 和 \(\sum\limits_{i<j}[p_i>p_j]\)，发现两者分别减小 \(2(j-i)\) 和 \(2(j-i)-1\)。因为最终两者全是 \(0\)，所以答案就是初始的 \(\sum|i-p_i|-\sum\limits_{i<j}[p_i>p_j]\)。

偷懒写了分块。

const int MAXN=5e5;
const int BLK=710;
int n,qu,p[MAXN+5],b[MAXN+5],blk_sz,blk_cnt,L[BLK+5],R[BLK+5],bel[MAXN+5];ll sum=0;
int calc_lt(int v,int l,int r){
	if(l>r)return 0;
	if(bel[l]==bel[r]){
		int sum=0;
		for(int i=l;i<=r;i++)sum+=(p[i]<v);
		return sum;
	}else{
		int sum=0;
		for(int i=l;i<=R[bel[l]];i++)sum+=(p[i]<v);
		for(int i=L[bel[r]];i<=r;i++)sum+=(p[i]<v);
		for(int i=bel[l]+1;i<bel[r];i++){
			int pos=lower_bound(b+L[i],b+R[i]+1,v)-b;
			sum+=pos-L[i];
		}return sum;
	}
}
void rebuild(int x){
	for(int i=L[x];i<=R[x];i++)b[i]=p[i];
	sort(b+L[x],b+R[x]+1);
}
int t[MAXN+5];
void add(int x,int v){for(int i=x;i;i&=(i-1))t[i]+=v;}
int query(int x){int ret=0;for(int i=x;i<=n;i+=(i&(-i)))ret+=t[i];return ret;}
int main(){
	scanf("%d%d",&n,&qu);blk_sz=(int)sqrt(n);blk_cnt=(n-1)/blk_sz+1;
	for(int i=1;i<=n;i++)scanf("%d",&p[i]),b[i]=p[i],sum+=abs(p[i]-i);
	for(int i=1;i<=blk_cnt;i++){
		L[i]=(i-1)*blk_sz+1;R[i]=min(i*blk_sz,n);
		for(int j=L[i];j<=R[i];j++)bel[j]=i;
	}
	for(int i=1;i<=blk_cnt;i++)sort(b+L[i],b+R[i]+1);
	for(int i=1;i<=n;i++)sum-=query(p[i]),add(p[i],1);
	while(qu--){
		int x,y;scanf("%d%d",&x,&y);if(x>y)swap(x,y);
		sum+=((p[x]<p[y])?-1:1);
		sum+=2*calc_lt(p[x],x+1,y-1);sum-=2*calc_lt(p[y],x+1,y-1);
		sum-=abs(x-p[x]);sum-=abs(y-p[y]);
		swap(p[x],p[y]);
		sum+=abs(x-p[x]);sum+=abs(y-p[y]);
		rebuild(bel[x]);rebuild(bel[y]);
		printf("%lld\n",sum);
	}
	return 0;
}
/*
8 0
8 2 1 5 3 4 7 6
*/

C