很好想的一个思路是：一个以排列好的数组，在开头添加一个数，那么需要互换的次数恰等于此数在数列中应有的rank值；而在末尾则是数组长度减去rank值。而一个混乱的序列在上一状态已经使用res的次数排成有序数列，因此每次插入一个值只需要通过rank改变res即可。
rank即为数列中有多少数小于它，这里需要注意有多少数小于它可以利用树状数组。这种计数题利用树状数组的+1，-1表示状态的情况很常见。
#include<iostream> #include<cstdlib> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int maxn=50005; struct node { int l,r,block,id; }q[maxn]; int n,m; int disc[maxn],a[maxn]; int ans[maxn]; int c[maxn]; int query(int x) { int res=0; for(int i=x;i;i-=i&-i)res+=c[i]; return res; } void add(int x,int val) { for(int i=x;i<=n;i+=i&-i)c[i]+=val; } bool cmp(node x,node y) { return x.block<y.block||(x.block==y.block&&x.r<y.r); } int main() { scanf("%d",&n); int bl=(int)sqrt(n); for(int i=1;i<=n;i++) scanf("%d",disc+i),a[i]=disc[i]; sort(disc+1,disc+n+1); for(int i=1;i<=n;i++) a[i]=lower_bound(disc+1,disc+n+1,a[i])-disc; scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%d%d",&q[i].l,&q[i].r); q[i].id=i; q[i].block=((q[i].l-1)/bl)+1; } sort(q+1,q+m+1,cmp); int l=1,r=0,res=0; for(int i=1;i<=m;i++) { while(l>q[i].l) { l--; res+=query(a[l]-1); add(a[l],1); } while(r<q[i].r) { r++; res+=r-l-query(a[r]-1); add(a[r],1); } while(l<q[i].l) { res-=query(a[l]-1); add(a[l],-1); l++; } while(r>q[i].r) { res-=r-l-query(a[r]-1); add(a[r],-1); r--; } ans[q[i].id]=res; } for(int i=1;i<=m;i++) printf("%d\n",ans[i]); return 0; }
