cdq分治经典例题，然而智商掉线傻逼错误坑了两天

原题：

对于序列A，它的逆序对数定义为满足i<j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

N<=100000 M<=50000

 

此题修改和询问绑定完全离线，可以直接倒序变成插入，然后就是三维数星星辣(ง •̀∀•́)ง

x为下标，y为值，z为时间轴，x排序，z_cdq分治，y树状数组

不用搞两次cdq分治，每次按x递增查找比y大的，然后按x递减查找比y小的

注意当x递增的时候查找的是比y大的，因为虽然x是递增，但是修改上去的都是比当前x小的

然后我先计算贡献再把小于mid的放左边大于mid的放右边然后进入下一层的做法是没有问题的

问题在于我傻逼题中删除的是值我删的是下标

注意longlong

代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 using namespace std; 9 #define ll long long10 int read(){ int z=0,mark=1; char ch=getchar();11 while(ch<'0'||ch>'9'){ if(ch=='-')mark=-1; ch=getchar();}12 while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0'; ch=getchar();}13 return z*mark;14 }15 struct cdd{ int x,y,z;}a[110000],q[110000];16 int n,m,b[110000]; int N;17 bool usd[110000]; int tt=0;18 ll e[110000]; int lbt[110000];19 ll ans[110000];20 int re[110000];21 void gtlbt(){ for(int i=1;i<=n;++i) lbt[i]=i&-i;}22 void mdf(int x,int y){ while(x<=n) e[x]+=y,x+=lbt[x];}23 ll qr(int x){ll bwl=0; while(x) bwl+=e[x],x-=lbt[x]; return bwl;}24 void cdq(int l,int r){25 if(l==r) return ;26 int md=(l+r)>>1;27 for(int i=l;i<=r;++i){28 if(a[i].z>md) mdf(a[i].y,1);29 else ans[a[i].z]+=qr(n)-qr(a[i].y);30 }31 for(int i=l;i<=r;++i)if(a[i].z>md) mdf(a[i].y,-1);32 for(int i=r;i>=l;--i){33 if(a[i].z>md) mdf(a[i].y,1);34 else ans[a[i].z]+=qr(a[i].y);35 }36 for(int i=l;i<=r;++i)if(a[i].z>md) mdf(a[i].y,-1);37 int t1=l,t2=md+1;38 for(int i=l;i<=r;++i) q[(a[i].z<=md?t1:t2)++]=a[i];39 for(int i=l;i<=r;++i) a[i]=q[i];40 cdq(l,md),cdq(md+1,r);41 }42 bool cmp(cdd x,cdd y){ return x.x
             
              >n>>m; N=n-m;46 gtlbt();47 for(int i=1;i<=n;++i) b[i]=read(),re[b[i]]=i;48 for(int i=1;i<=m;++i) a[++tt].y=read(),a[i].x=re[a[i].y],a[i].z=i,usd[a[i].x]=true;49 for(int i=1;i<=n;++i)if(!usd[i]) a[++tt].x=i,a[tt].y=b[i],a[tt].z=tt;50 sort(a+1,a+n+1,cmp);51 cdq(1,n);52 for(int i=n;i>1;--i) ans[i-1]+=ans[i];53 for(int i=1;i<=m;++i) printf("%I64d\n",ans[i]);54 return 0;55 }