P1975 [国家集训队]排队
对于一个长度为 n 的序列进行 k 次操作，每次操作都是交换序列中的某两个数。对于每一个操作，回答当前序列中有多少个逆序对。
树状数组套权值线段树直接维护，考虑每次修改的贡献即可。
view code
#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=false;
while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
const int N=2e5+1,M=3e7+1;
int n,Q,a[N],b[N],rt[N];
long long ans;
int ls[M],rs[M],tot,val[M];
void Modify(int &now,int l,int r,int x,int k){
if(!now) now=++tot;
val[now]+=k;
if(l==r)return;
int mid=l+r>>1;
if(x<=mid) Modify(ls[now],l,mid,x,k);
else Modify(rs[now],mid+1,r,x,k);
}
int qa[N],qb[N];
inline long long Query(int l,int r,int x,int type){
int cnta=0,cntb=0;
long long ans=0;
for(int i=l-1;i;i-=i&-i) qa[++cnta]=rt[i];
for(int i=r;i;i-=i&-i) qb[++cntb]=rt[i];
l=1,r=n;
while(l<r){
int mid=l+r>>1;
if(x>mid){
if(type){
for(int i=1;i<=cnta;i++) ans-=val[ls[qa[i]]];
for(int i=1;i<=cntb;i++) ans+=val[ls[qb[i]]];
}
for(int i=1;i<=cnta;i++) qa[i]=rs[qa[i]];
for(int i=1;i<=cntb;i++) qb[i]=rs[qb[i]];
l=mid+1;
}
else{
if(!type){
for(int i=1;i<=cnta;i++) ans-=val[rs[qa[i]]];
for(int i=1;i<=cntb;i++) ans+=val[rs[qb[i]]];
}
for(int i=1;i<=cnta;i++) qa[i]=ls[qa[i]];
for(int i=1;i<=cntb;i++) qb[i]=ls[qb[i]];
r=mid;
}
}
return ans;
}
signed main(){
read(n);
for(int i=1;i<=n;i++) read(a[i]),b[i]=a[i];
sort(b+1,b+n+1);
int cnt=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+cnt,a[i])-b;
for(int i=1;i<=n;i++){
ans+=Query(1,i-1,a[i],0);
for(int j=i;j<=n;j+=j&-j) Modify(rt[j],1,n,a[i],1);
}
write(ans),putchar('
');
read(Q);
while(Q--){
int x,y;read(x),read(y);
if(x==y){write(ans),putchar('
');continue;}
if(x>y)swap(x,y);
ans=ans-Query(1,x-1,a[x],0)-Query(x+1,n,a[x],1)-Query(1,y-1,a[y],0)-Query(y+1,n,a[y],1);
for(int i=x;i<=n;i+=i&-i) Modify(rt[i],1,n,a[x],-1),Modify(rt[i],1,n,a[y],1);
for(int i=y;i<=n;i+=i&-i) Modify(rt[i],1,n,a[x],1),Modify(rt[i],1,n,a[y],-1);
swap(a[x],a[y]);
ans=ans+Query(1,x-1,a[x],0)+Query(x+1,n,a[x],1)+Query(1,y-1,a[y],0)+Query(y+1,n,a[y],1);
if(a[x]<a[y]) ans+=1;
else if(a[x]>a[y]) ans-=1;
write(ans),putchar('
');
}
return 0;
}