删除的话可以反过来看 看作是插入 这样就成了一个正常序列的操作
按照时间cdq分治即可
注意答案要进行前缀和 因为得出的是某个元素的点对 要求的是整个序列的
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// const int N=1e7+10; int n,m,cnt,t[N],a[N],pos[N],vis[N],x; ll ans[N]; void add(int x,int v){for(;x<=N;x+=x&-x)t[x]+=v;} int qsum(int x){int ans=0;for(;x;x-=x&-x)ans+=t[x];return ans;} struct node { int pos,v,id; }s[N]; bool cmp(node a,node b){return a.pos<b.pos;} void cdq(int l,int r) { if(l==r)return ;int mid=(l+r)>>1; cdq(l,mid);cdq(mid+1,r); sort(s+l,s+mid+1,cmp);sort(s+mid+1,s+r+1,cmp); int j=l; rep(i,mid+1,r) { while(j<=mid&&s[j].pos<=s[i].pos)add(s[j].v,1),j++; ans[s[i].id]+=1ll*(qsum(N)-qsum(s[i].v)); } while(--j>=l)add(s[j].v,-1); j=mid; repp(i,r,mid+1) { while(j>=l&&s[j].pos>=s[i].pos)add(s[j].v,1),j--; ans[s[i].id]+=1ll*qsum(s[i].v); } while(++j<=mid)add(s[j].v,-1); } int main() { int n,m;scanf("%d%d",&n,&m); rep(i,1,n)scanf("%d",&x),pos[x]=i; rep(i,1,m)scanf("%d",&a[i]),vis[a[i]]=1; rep(i,1,n) if(!vis[i]) s[++cnt]=(node){pos[i],i,0}; repp(i,m,1) s[++cnt]=(node){pos[a[i]],a[i],i}; cdq(1,cnt); repp(i,m-1,1)ans[i]+=ans[i+1]; rep(i,1,m) printf("%lld ",ans[i]+ans[0]); return 0; }