考虑一次交换，我们发现，被选出来的 \([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]);
}
}