Description

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

Solution

比较明显的CDQ分治维护三维偏序

将删除操作倒过来变成插入，要求的也就是tim[i]<tim[j],pos[i]<pos[j],a[i]>a[j]和tim[i]<tim[j],pos[i]>pos[j],x[i]<x[j]的数量

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define N 100005#define M 50005using namespace std;typedef long long LL;int n,m,a[N],c[N],p[N],sign[N],res[N],tim=0;bool del[N];inline int read(){    int x=0,f=1;char c=getchar();    while(c<'0'||c>'9'){
   if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}struct Node{    int x,id,pos;    Node(int x=0,int id=0,int pos=0):x(x),id(id),pos(pos){}    bool operator < (const Node a) const    {
    return pos>a.pos;}}O[N],t[N];bool cmp(Node a,Node b){
   return a.id
          
           0) { if(sign[pos]==tim)res+=c[pos]; pos-=lowbit(pos); } return res;}void merge(int l,int r){ if(l==r)return; int mid=(l+r)>>1; int i=l,j=mid+1,k=l; while(i<=mid&&j<=r) { if(O[i].pos>O[j].pos)t[k++]=O[i++]; else t[k++]=O[j++]; } while(i<=mid)t[k++]=O[i++]; while(j<=r)t[k++]=O[j++]; memcpy(O+l,t+l,sizeof(Node)*(r-l+1));//for(int i=1;i<=r;i++)O[i]=t[i];}void solve(int l,int r){ if(l==r)return; int mid=(l+r)>>1; for(int i=l,j=mid+1,k=l;k<=r;k++) if(O[k].id<=mid)t[i++]=O[k]; else t[j++]=O[k]; memcpy(O+l,t+l,sizeof(Node)*(r-l+1));//for(int i=l;i<=r;i++)O[i]=t[i]; solve(l,mid); int j=l;tim++; for(int i=mid+1;i<=r;i++) { while(O[j].pos>O[i].pos&&j<=mid) add(O[j].x,1),j++; if(O[i].id>n-m)res[O[i].id]+=query(O[i].x); } j=mid;tim++;int cnt=0; for(int i=r;i>mid;i--) { while(O[j].pos
           
            =l) add(O[j].x,1),j--,cnt++; if(O[i].id>n-m)res[O[i].id]+=cnt-query(O[i].x); } solve(mid+1,r); merge(l,r);}int main(){ n=read(),m=read(); for(int i=1;i<=n;i++)a[i]=read(),p[a[i]]=i; for(int i=m;i>0;i--) { int x=read(); O[i+n-m]=Node(x,i+n-m,p[x]); del[x]=1; } int cnt=0;LL ans=0; for(int i=1;i<=n;i++) if(!del[a[i]]) { ++cnt,O[cnt]=Node(a[i],cnt,p[a[i]]); add(a[i],1); ans+=cnt-query(a[i]); } sort(O+1,O+1+n),solve(1,n); for(int i=1;i<=n;i++)ans+=res[i]; for(int i=n;i>n-m;i--) {printf("%lld\n",ans);ans-=res[i];} return 0;}
           
          
         
        
       
      
     

T了很多发，以为是被卡常了（后来证明也确实是被卡常了【？）发现是因为自己memcpy一直写的是循环赋值…手动再见