动态逆序对
- 加多一维时间戳，时间戳越大越早删除
cpp
struct Node{
int val,ts,res;
bool operator<(const Node&tmp)const{
if(val!=tmp.val)return val<tmp.val;
return ts<tmp.ts;
}
};
int t[N];
void add(int x,int y){
for(int i=x;i<N;i+=i&-i)t[i]+=y;
}
int query(int x){
int ans=0;
for(int i=x;i;i&=i-1)ans+=t[i];
return ans;
}
vector<Node> a,b;
void msort(int l,int r){
if(l==r)return;
int mid=l+r>>1;
msort(l,mid),msort(mid+1,r);
int i=mid,j=r,k=l;
//t[i]<t[j],pos[i]<pos[j],A[i]>A[j]
while(i>=l&&j>mid){
//val值从小到大排序，因此这里倒序枚举
if(a[i].val>a[j].val)add(a[i].ts,1),i--;
else a[j].res+=query(a[j].ts-1),j--;
}
while(i>=l)add(a[i].ts,1),i--;
while(j>mid)a[j].res+=query(a[j].ts-1),j--;
for(int i=l;i<=mid;i++)add(a[i].ts,-1);
j=l,i=mid+1;
//t[i]<t[j],pos[i]>pos[j],A[i]<A[j]
while(j<=mid&&i<=r){
if(a[i].val<a[j].val)add(a[i].ts,1),i++;
else a[j].res+=query(a[j].ts-1),j++;
}
while(j<=mid)a[j].res+=query(a[j].ts-1),j++;
while(i<=r)add(a[i].ts,1),i++;
for(int i=mid+1;i<=r;i++)add(a[i].ts,-1);
i=l,j=mid+1;
//归并排序
while(i<=mid&&j<=r){
if(a[i].val<a[j].val)b[k++]=a[i++];
else b[k++]=a[j++];
}
while(i<=mid)b[k++]=a[i++];
while(j<=r)b[k++]=a[j++];
for(int i=l;i<=r;i++)a[i]=b[i];
}
void solve(){
int n,m;
cin>>n>>m;
vector<int> pos(n+1);
for(int i=0;i<n;i++){
int x;
cin>>x;
pos[x]=i;
a.push_back({x,0});
}
int ts=n;
for(int i=1;i<=m;i++){
int x;
cin>>x;
a[pos[x]].ts=ts--;
}
for(int i=0;i<n;i++){
if(a[i].ts==0)a[i].ts=ts--;
}
b=a;
msort(0,n-1);
vector<int> ans(n+1);
for(int i=0;i<n;i++)ans[a[i].ts]+=a[i].res;
for(int i=1;i<=n;i++)ans[i]+=ans[i-1];
for(int i=n;i>n-m;i--)cout<<ans[i]<<"\n";
}