题目链接：https://www.luogu.org/problemnew/show/P1393
题解：把这个转化成三维，使用cdq分治来解决，第一维为删除的时间（不删除的为n+1），第二维是以位置，第三维就是数值。
代码：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll maxn=1e5+5; ll xx[maxn];ll n,m; ll lowbit(ll x) { return x&(-x); } void add(ll x,ll val) { while(x<=n) { xx[x]+=val; x+=lowbit(x); } } ll query(ll x) { ll ans=0; while(x) { ans+=xx[x]; x-=lowbit(x); } return ans; } struct node { ll ti,id,val,ans; }s[maxn]; ll p[maxn],x[maxn],de[maxn]; ll mm[maxn]; ll cmp1(node pp,node qq) { return pp.ti>qq.ti; } ll cmp2(node pp,node qq) { return pp.id<qq.id; } void solve(ll l,ll r) { if(l==r) return ; ll mid=(l+r)>>1; solve(l,mid);solve(mid+1,r); sort(s+l,s+1+mid,cmp2);sort(s+mid+1,s+1+r,cmp2); ll j=l; for(ll i=mid+1;i<=r;i++) { while(j<=mid&&s[j].id<s[i].id) add(s[j].val,1),j++; s[i].ans+=query(n)-query(s[i].val); } for(ll i=l;i<j;i++) add(s[i].val,-1); j=mid; for(ll i=r;i>=mid+1;i--) { while(j>=l&&s[j].id>s[i].id) add(s[j].val,1),j--; s[i].ans+=query(s[i].val-1); } for(ll i=mid;i>j;i--) add(s[i].val,-1); } int main() { cin>>n>>m; for(ll i=1;i<=n;i++) { cin>>x[i]; p[i]=x[i]; } sort(p+1,p+1+n); for(ll i=1;i<=n;i++) x[i]=lower_bound(p+1,p+1+n,x[i])-p; ll ans=0; for(ll i=n;i>=1;i--) { add(x[i],1); ans+=query(x[i]-1); } for(ll i=1;i<=n;i++) add(x[i],-1); for(ll i=1;i<=n;i++) s[i]=node{n+1,i,x[i],0}; for(ll i=1;i<=m;i++) { cin>>de[i]; s[de[i]].ti=i; } sort(s+1,s+1+n,cmp1); solve(1,n); for(ll i=1;i<=n;i++) mm[s[i].id]=s[i].ans; //for(int i=1;i<=n;i++) cout<<mm[i]<<' ';cout<<endl; cout<<ans; for(ll i=1;i<=m;i++) { ans-=mm[de[i]]; cout<<' '<<ans; } cout<<endl; return 0; }
