Link
Description
给定一个排列，每次删除一个元素，输出当前逆序对个数。
Solution
原序列的逆序对个数很好求。现在考虑删除一个数对答案的贡献。对每个元素，我们记一个它的大小 (v)，它在序列中的位置下标 (pos)，它被删除的时间 (t)，对于没有被删除的元素，其删除时间设为 (m+1)，即删除的元素个数加一。那么删除一个下标为 (i) 数会减少的逆序对个数就可以按下标大小分成两半来求。
[egin{cases}
i<j \
v_i>v_j \
t_i<t_j
end{cases}
quad
egin{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
",ans);
ans-=a[i].ans;
}
}