http://www.lydsy.com/JudgeOnline/problem.php?id=3289 是离线的好开心啊 为什么说开心呢，这种题，碰到离线，就可以莫队了呀 求逆序对嘛，来发树状数组 首先我们可以求出1~i-1区间内比i大的数，然后前缀和搞搞就是啦 接下来交给分块莫队 ps：一开始T了n发找不到问题后来才发现是块搞错了。。。
#include<bits/stdc++.h> using namespace std; inline int read(){ int k=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();} return k*f; } struct ppap{ int l,r,x,k; }t[50001]; unsigned int ans[50001]; int n,m,a[50001],b[50001],f[50001]; inline int erfen(int x,int sum){ int l=1,r=sum; while(l<=r){ int mid=(l+r)>>1; if(b[mid]==x)return mid; if(b[mid]>x)r=mid-1; else l=mid+1; } return 0; } inline bool cmp(ppap a,ppap b){return a.k==b.k?a.r<b.r:a.k<b.k;} inline int lowbit(int x){return x&-x;} inline void add(int x,int v){for(int i=x;i<=n;i+=lowbit(i))f[i]+=v;} inline int sum(int x){unsigned int ans=0;for(int i=x;i;i-=lowbit(i))ans+=f[i];return ans;} inline void work(){ int l=1,r=0;unsigned int now=0; for(int i=1;i<=m;i++){ while(l<t[i].l)add(a[l],-1),now-=sum(a[l]-1),l++; while(r>t[i].r)add(a[r],-1),now-=r-l-sum(a[r]),r--; while(l>t[i].l)l--,add(a[l],1),now+=sum(a[l]-1); while(r<t[i].r)r++,add(a[r],1),now+=r-l+1-sum(a[r]); ans[t[i].x]=now; } } int main() { n=read();int sum=n; int p=sqrt(n); for(int i=1;i<=n;i++)b[i]=a[i]=read(); sort(b+1,b+n+1); for(int i=2;i<=sum;i++)if(b[i]==b[i-1]){ sum--;for(int j=i;j<=sum;j++)b[j]=b[j+1];i--; } for(int i=1;i<=n;i++)a[i]=erfen(a[i],sum); m=read(); for(int i=1;i<=m;i++){ t[i].l=read();t[i].r=read();t[i].x=i;t[i].k=(t[i].l-1)/p+1; } sort(t+1,t+m+1,cmp); work(); for(int i=1;i<=m;i++)printf("%d\n",ans[i]); return 0; }