这种题肯定首先要寻找不变量。
显然后面排好序的后缀不会被改变。因此从整体上来看我们的流程肯定是，如果当前 \(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