md第一道在NOILinux 下用vim做的紫题。由于我对这个操作系统不是很熟悉，似乎有什么地方搞错了，md调死。（我还打了两遍代码，调了两个小时）
但是这道题并不难，就是树状数组套上主席树……这应该是带修改主席树的套路，可以同时满足逆序对要求的位置和大小两个条件。
不过还是调了很长时间……反映出我数据结构方面的能力极为薄弱
最后放代码
#include<cstdio> #include<algorithm> #include<cstring> #include<cctype> #include<cstdlib> #define maxn 500020 #define mid ((l+r)>>1) inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch==‘-‘) f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-‘0‘; ch=getchar(); } return num*f; } int sum[maxn*15]; int rt[maxn*15]; int ls[maxn*15]; int rs[maxn*15]; int c[maxn*15]; int q[maxn],back[maxn]; int x[maxn],y[maxn]; int a1[maxn],a2[maxn]; int n,m; int tot; inline int low(int i){ return i&(-i); } inline int ask(int pos){ int ans=0; while(pos){ ans+=c[pos]; pos-=low(pos); } return ans; } int querypre(int from,int to,int e){ int l=1,r=n;int totx=0,toty=0,ans=0; from--; for(int i=from;i;i-=low(i)) x[++totx]=rt[i]; for(int i=to;i;i-=low(i)) y[++toty]=rt[i]; while(l<r){ if(e>mid){ for(int i=1;i<=totx;++i) ans-=sum[ls[x[i]]]; for(int i=1;i<=toty;++i) ans+=sum[ls[y[i]]]; for(int i=1;i<=totx;++i) x[i]=rs[x[i]]; for(int i=1;i<=toty;++i) y[i]=rs[y[i]]; l=mid+1; } else{ for(int i=1;i<=totx;++i) x[i]=ls[x[i]]; for(int i=1;i<=toty;++i) y[i]=ls[y[i]]; r=mid; } } return ans; } int querysub(int from,int to,int e){ int l=1,r=n;int totx=0,toty=0,ans=0; from--; for(int i=from;i;i-=low(i)) x[++totx]=rt[i]; for(int i=to;i;i-=low(i)) y[++toty]=rt[i]; while(l<r){ if(e<=mid){ for(int i=1;i<=totx;++i) ans-=sum[rs[x[i]]]; for(int i=1;i<=toty;++i) ans+=sum[rs[y[i]]]; for(int i=1;i<=totx;++i) x[i]=ls[x[i]]; for(int i=1;i<=toty;++i) y[i]=ls[y[i]]; r=mid; } else{ for(int i=1;i<=totx;++i) x[i]=rs[x[i]]; for(int i=1;i<=toty;++i) y[i]=rs[y[i]]; l=mid+1; } } return ans; } void update(int &o,int l,int r,int p){ if(!o) o=++tot; sum[o]++; if(l==r) return; if(p<=mid) update(ls[o],l,mid,p); else update(rs[o],mid+1,r,p); } int main(){ n=read(),m=read(); for(int i=1;i<=n;++i){ q[i]=read();back[q[i]]=i; } long long ans=0; for(int i=1;i<=n;++i){ a1[i]=ask(n)-ask(q[i]); ans+=a1[i]; for(int j=q[i];j<=n;j+=low(j)) c[j]++; } memset(c,0,sizeof(c)); for(int i=n;i;--i){ a2[i]=ask(q[i]-1); for(int j=q[i];j<=n;j+=low(j)) c[j]++; } for(int i=1;i<=m;++i){ printf("%lld\n",ans); int pos=read();pos=back[pos]; ans-=(a1[pos]+a2[pos]-querypre(pos+1,n,q[pos])-querysub(1,pos-1,q[pos])); for(int j=pos;j<=n;j+=low(j)) update(rt[j],1,n,q[pos]); } return 0; }