传送门
题意： 对于序列A，它的逆序对数定义为满足i< j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。
题解： 首先删除看做为逆向加点，记三元组 (pos,val,time) 。那么一个在 timei 时刻加入的点i会对所有 timei 以后的点产生贡献，这个贡献为 timej<i,posj<posi,valj>vali 的 j 的个数加上timej<i,posj>posi,valj<vali的个数，又是三维偏序，CDQ经典的解法。 （注意：没有删除过的点要先处理出有多少逆序对）。
Code: #include<bits/stdc++.h> using namespace std; const int Maxn=1e5+50; typedef long long ll; streambuf *ib,*ob; inline int read() { char ch=ib->sbumpc();int i=0,f=1; while(!isdigit(ch)){if(ch=='-')f=-1;ch=ib->sbumpc();} while(isdigit(ch)){i=(i<<1)+(i<<3)+ch-'0';ch=ib->sbumpc();} return i*f; } int buf[50]; inline void W(ll x) { if(!x){ob->sputc('0');return;} if(x<0){ob->sputc('-');x=-x;} while(x)buf[++buf[0]]=x%10,x/=10; while(buf[0])ob->sputc(buf[buf[0]--]+'0'); } int n,m,id[Maxn]; ll ans[Maxn],bit[Maxn]; struct node { int val,t; }q1[Maxn],q2[Maxn],tmp[Maxn]; inline void insert(int pos,int val){for(;pos<=n;pos+=(pos&(-pos)))bit[pos]+=val;} inline int query(int pos) { int res=0; for(;pos;pos-=(pos&(-pos)))res+=bit[pos]; return res; } inline void solve(int l,int r) { static int v[Maxn]; if(l==r)return; int mid=(l+r)>>1; solve(l,mid); solve(mid+1,r); int head1=l,head2=mid+1,pos=l; for(int i=l;i<=r;i++)tmp[i]=q1[i]; while(head1<=mid&&head2<=r) { if(tmp[head1].val>tmp[head2].val) { insert(tmp[head1].t,1); q1[pos++]=tmp[head1++]; } else { if(tmp[head2].t!=1)ans[tmp[head2].t]+=query(tmp[head2].t); q1[pos++]=tmp[head2++]; } } while(head1<=mid) { insert(tmp[head1].t,1); q1[pos++]=tmp[head1++]; } while(head2<=r) { if(tmp[head2].t!=1)ans[tmp[head2].t]+=query(tmp[head2].t); q1[pos++]=tmp[head2++]; } for(int i=l;i<=mid;i++)insert(tmp[i].t,-1); head1=l,head2=mid+1,pos=l; for(int i=l;i<=r;i++)tmp[i]=q2[i]; while(head1<=mid&&head2<=r) { if(tmp[head1].val<tmp[head2].val) { insert(tmp[head1].t,1); q2[pos++]=tmp[head1++]; } else { if(tmp[head2].t!=1)ans[tmp[head2].t]+=query(tmp[head2].t); q2[pos++]=tmp[head2++]; } } while(head1<=mid) { insert(tmp[head1].t,1); q2[pos++]=tmp[head1++]; } while(head2<=r) { if(tmp[head2].t!=1)ans[tmp[head2].t]+=query(tmp[head2].t); q2[pos++]=tmp[head2++]; } for(int i=l;i<=mid;i++)insert(tmp[i].t,-1); } int main() { ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);ib=cin.rdbuf();ob=cout.rdbuf(); n=read(),m=read(); for(int i=1;i<=n;i++){q1[i].val=read();q1[i].t=1;id[q1[i].val]=i;q2[n-i+1]=q1[i];} for(int i=m;i>=1;i--){int p=id[read()];q1[p].t=q2[n-p+1].t=i+1;} for(int i=1;i<=n;i++) { if(q2[i].t!=1)continue; ans[1]+=query(q2[i].val);insert(q2[i].val,1); } memset(bit,0,sizeof(bit)); solve(1,n); for(int i=1;i<=m;i++)ans[i+1]+=ans[i]; for(int i=m;i>=1;i--)W(ans[i+1]),ob->sputc('\n'); }