题目 Sample Input 4 1 4 2 3 2 1 2 2 4 Sample Output 0 2
样例解释：第一天，Mato不需要交换 。第二天，Mato可以把2号交换2次移到最后。
/************************************************************** 3289: Mato的文件管理 Time Limit: 40 Sec Memory Limit: 128 MB Time:8064 ms Memory:3844 kb ****************************************************************/ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cmath> #define en '\n' #define foru(i,a,b) for(int i=a;i<=b;++i) #define low(i) i&-i #define m(a,b) memset(a,b,sizeof a) using namespace std; typedef long long ll; const int N=5e4+5,M=N,INF=0x3f3f3f3f; template<class T>void rd(T &x) { x=0;int f=0;char ch=getchar(); while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x=f?-x:x; return; } int pos[N],tot;ll refl[N],a[N],c[N]; int bl[N],dexl,dexr,block;ll res; ll ans[M]; struct Query{int id,l,r;}q[M]; bool cmp(Query x,Query y) { if(x.l/block==y.l/block) return x.r<y.r; return x.l/block<y.l/block; } void modify(int x,int val) { while(x<=tot) c[x]+=val,x+=low(x); } ll getsum(int x) { ll tmp=0; while(x) tmp+=c[x],x-=low(x); return tmp; } void add(int x,int f) { int k=pos[x]; modify(k,1); if(!f)//多了一个r,要找r前面比a[r]大的. res+=(dexr-dexl+1)-getsum(k); else//多了一个l,要找l后面比a[l]小的. if(k!=1) res+=getsum(k-1); } void del(int x,int f) { int k=pos[x]; modify(k,-1); if(!f)//少了一个r,要找r前面比a[r]大的. res-=(dexr-dexl+1)-getsum(k); else//少了一个l,要找后面有多少比a[l]小的. if(k!=1) res-=getsum(k-1); } int main() { int n;rd(n);block=sqrt(n); foru(i,1,n) rd(a[i]),refl[i]=a[i]; sort(refl+1,refl+n+1); tot=unique(refl+1,refl+n+1)-(refl+1); foru(i,1,n) pos[i]=lower_bound(refl+1,refl+tot+1,a[i])-refl; int m;rd(m); foru(i,1,m) rd(q[i].l),rd(q[i].r),q[i].id=i; sort(q+1,q+m+1,cmp); dexl=1,dexr=0,res=0; foru(i,1,m) { while(dexr<q[i].r) add(++dexr,0); while(dexl>q[i].l) add(--dexl,1); while(dexr>q[i].r) del(dexr--,0); while(dexl<q[i].l) del(dexl++,1); ans[q[i].id]=res; } foru(i,1,m) printf("%d\n",ans[i]); }