【传送门：BZOJ2141】
简要题意：
给出一个长度为n的序列，一开始先求出逆序对数
然后给出m个操作，每个操作输入l,r，要求交换第l和第r个数，然后再求出逆序对数
题解：
树状数组处理逆序对数问题
因为每次交换l和r的时候，实际上除了l到r的区间外，其他是不受影响的，所以我们分块来处理
然后树状数组维护就好了
注意l不一定大于r，而且可能有相同的值
参考代码：
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> using namespace std; int a[210][21000]; int belong[21000],L[210],R[210]; int tot; int lowbit(int x){return x&-x;} void change(int i,int x,int d) { while(x<=tot) { a[i][x]+=d; x+=lowbit(x); } } int getsum(int i,int x) { int ans=0; while(x!=0) { ans+=a[i][x]; x-=lowbit(x); } return ans; } struct node { int d,id,s; }h[21000]; bool cmp1(node n1,node n2) { return n1.d<n2.d; } bool cmp2(node n1,node n2) { return n1.id<n2.id; } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&h[i].d); h[i].id=i; } sort(h+1,h+n+1,cmp1); tot=0; for(int i=1;i<=n;i++) { if(h[i-1].d!=h[i].d) tot++; h[i].s=tot; } sort(h+1,h+n+1,cmp2); int ans=0; for(int i=n;i>=1;i--) { ans+=getsum(0,h[i].s-1); change(0,h[i].s,1); } printf("%d ",ans); int block=int(sqrt(n)); for(int i=1;i<=n;i++) { int t=(i-1)/block+1; belong[i]=t; if(L[t]==0) R[t-1]=i-1,L[t]=i; } R[belong[n]]=n; for(int i=1;i<=n;i++) change(belong[i],h[i].s,1); int m;scanf("%d",&m); for(int t=1;t<=m;t++) { int l,r; scanf("%d%d",&l,&r);if(l>r) swap(l,r); int bl=belong[l],br=belong[r]; if(bl==br) { for(int i=l+1;i<=r-1;i++) { if(h[l].s>h[i].s) ans--; if(h[l].s<h[i].s) ans++; if(h[r].s>h[i].s) ans++; if(h[r].s<h[i].s) ans--; } } else { for(int i=bl+1;i<=br-1;i++) { ans-=getsum(i,h[l].s-1); ans+=getsum(i,tot)-getsum(i,h[l].s); ans+=getsum(i,h[r].s-1); ans-=getsum(i,tot)-getsum(i,h[r].s); } for(int i=l+1;i<=R[bl];i++) { if(h[l].s>h[i].s) ans--; if(h[l].s<h[i].s) ans++; if(h[r].s>h[i].s) ans++; if(h[r].s<h[i].s) ans--; } for(int i=L[br];i<=r-1;i++) { if(h[l].s>h[i].s) ans--; if(h[l].s<h[i].s) ans++; if(h[r].s>h[i].s) ans++; if(h[r].s<h[i].s) ans--; } } if(h[l].s>h[r].s) ans--; if(h[l].s<h[r].s) ans++; change(bl,h[l].s,-1); change(bl,h[r].s,1); change(br,h[r].s,-1); change(br,h[l].s,1); swap(h[l],h[r]); printf("%d ",ans); } return 0; }