题目大意
给出一个序列,之后删除\(M\) 个点,求删除每个点后的逆序对数
solve
这道题的解法很多,我就用比较优秀的cdq解法
根据逆序对的定义,产生贡献的点对 \((i,j)\) 满足 \(T_i<T_j \& A_i>A_j \& X_i<X_j\) 或者 \(T_i<T_j \& A_i<A_j \& X_i>X_j\)
于是就变成了一个三维偏序问题,可以使用 \(CDQ\) 算法,我们考虑每个数 \(i\) 产生的贡献
在分治过程中,用树状数组统计之前比我大的, 或者后面比我小的,对于删除操作,可以用 $add_x(x,-1) $来撤销之前的操作
code
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
inline int read(){
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
struct qus{
int m,v,d,id,t;
}Q[maxn<<1];
int N,M,tot,c[maxn],a[maxn],pos[maxn];
long long ans[maxn];
bool cmp1(qus x,qus y){return x.d<y.d;}
void add_x(int x,int data){
for(int i=x;i<=N;i+=i&-i)c[i]+=data;
}
int get(int x){
int ret=0;
for(int i=x;i;i-=i&-i)ret+=c[i];
return ret;
}
void CDQ(int l,int r){
if(l==r)return ;
int mid=(l+r)>>1,j=l;
CDQ(l,mid),CDQ(mid+1,r);
sort(Q+l,Q+mid+1,cmp1);sort(Q+mid+1,Q+r+1,cmp1);
for(int i=mid+1;i<=r;i++){
while(j<=mid&&Q[j].d<=Q[i].d) add_x(Q[j].v,Q[j].m),j++;
ans[Q[i].id]+=Q[i].m*(get(N)-get(Q[i].v));
}
for(int i=l;i<j;i++) add_x(Q[i].v,-Q[i].m);
j=mid;
for(int i=r;i>mid;--i){
while(j>=l&&Q[j].d>=Q[i].d)add_x(Q[j].v,Q[j].m),j--;
ans[Q[i].id]+=Q[i].m*get(Q[i].v-1);
}
for(int i=mid;i>j;i--)add_x(Q[i].v,-Q[i].m);
}
int main(){
freopen("P3157.in","r",stdin);
freopen("P3157.out","w",stdout);
N=read();M=read();
for(int i=1;i<=N;i++)a[i]=read(),pos[a[i]]=i,Q[++tot]=(qus){1,a[i],i,0,tot};
for(int i=1,x;i<=M;i++)x=read(),Q[++tot]=(qus){-1,x,pos[x],i,tot};
CDQ(1,tot);
for(int i=1;i<=M;i++) ans[i]+=ans[i-1];
for(int i=0;i<M;i++) printf("%lld\n",ans[i]);
return 0;
}