Link

Description

给定一个排列，每次删除一个元素，输出当前逆序对个数。

Solution

原序列的逆序对个数很好求。现在考虑删除一个数对答案的贡献。对每个元素，我们记一个它的大小 \(v\)，它在序列中的位置下标 \(pos\)，它被删除的时间 \(t\)，对于没有被删除的元素，其删除时间设为 \(m+1\)，即删除的元素个数加一。那么删除一个下标为 \(i\) 数会减少的逆序对个数就可以按下标大小分成两半来求。

\[\begin{cases} i<j \\ v_i>v_j \\ t_i<t_j \end{cases} \quad \begin{cases} i>j \\ v_i<v_j \\ t_i<t_j \end{cases} \]

容易发现都是三维偏序，直接 CDQ 分治即可。

#include<stdio.h>
#include<algorithm>
using namespace std;
#define N 100007
#define ll long long

inline int read(){
    int x=0,flag=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') flag=0;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
    return flag? x:-x;
}

struct Node{
    int pos,t,val;
    ll ans;
}a[N];

ll c[N];
int n,m,D[N];

inline int lowbit(int x){return (-x)&x;}
inline void add(int x,ll v){while(x<=n)c[x]+=v,x+=lowbit(x);}
inline ll query(int x){ll ret=0;while(x)ret+=c[x],x-=lowbit(x);return ret;}

inline bool Cmp1(const Node &X,const Node &Y){return X.t!=Y.t? X.t>Y.t:X.pos>Y.pos;}
inline bool Cmp2(const Node &X,const Node &Y){return X.pos>Y.pos;}
inline bool Cmp3(const Node &X,const Node &Y){return X.val>Y.val;}

void CDQ(int lf,int rf){
    if(lf==rf) return ;
    int mid=(lf+rf)>>1;
    CDQ(lf,mid),CDQ(mid+1,rf);
    sort(a+lf,a+mid+1,Cmp2),sort(a+mid+1,a+rf+1,Cmp2);
    int i=mid+1,j=lf-1;
    for(;i<=rf;i++){
        while(j<mid&&a[j+1].pos>a[i].pos)
            ++j,add(a[j].val,1);
        a[i].ans+=query(a[i].val-1);
    }
    for(i=lf;i<=j;i++) add(a[i].val,-1);
    sort(a+lf,a+mid+1,Cmp3),sort(a+mid+1,a+rf+1,Cmp3);
    i=mid+1,j=lf-1;
    for(;i<=rf;i++){
        while(j<mid&&a[j+1].val>a[i].val)
            ++j,add(a[j].pos,1);
        a[i].ans+=query(a[i].pos-1);
    }
    for(i=lf;i<=j;i++) add(a[i].pos,-1);
}

int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i].val=read(),D[a[i].val]=a[i].pos=i;
    for(int i=1;i<=m;i++) a[D[read()]].t=i;
    for(int i=1;i<=n;i++) if(!a[i].t) a[i].t=m+1;
    ll ans=0;
    for(int i=1;i<=n;i++){
        ans+=query(n-a[i].val+1);
        add(n-a[i].val+1,1);
    }
    for(int i=1;i<=n;i++) c[i]=0;
    sort(a+1,a+1+n,Cmp1),CDQ(1,n);
    sort(a+1,a+1+n,Cmp1);
    for(int i=n;i>n-m;i--){
        printf("%lld\n",ans);
        ans-=a[i].ans;
    }
}