容易看出ans[i]=ans[i-1]-q[i],q[i]为删去第i个数减少的逆序对。
先用树状数组算出最开始的逆序对，预处理出每个数前边比它大的和后边比它小的，就求出了q[i]的初始值。
设b[i]是第i个删除的数，pos[i]为i在数列里的位置。
对q[i]产生影响的是 1. j<i,pos[b[j]]<pos[b[i]],b[j]>b[i]. 2.j<i,pos[b[j]]>pos[b[i]],b[j]<b[i].
因为是三维的，所以我们套一层cdq。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
#define N 100005
using namespace std;
int n,m;
int a[N],b[N],d[N];
int c[N];
int ans[N];int p[N];
int qur(int x)
{
int tp=;
for(int i=x;i;i-=(i&-i))tp+=c[i];
return tp;
}
void add(int x,int z)
{
for(int i=x;i<=n;i+=(i&-i))c[i]+=z;
return ;
}
int tmp[N];int q[N];
bool cmp(int x,int y)
{
return p[x]<p[y];
}
void solve(int l,int r)
{
if(l==r)return ;
int mid=(l+r)>>;
int cnt=;
for(int i=l;i<=r;i++)tmp[++cnt]=b[i];
sort(tmp+,tmp+cnt+,cmp);
for(int i=;i<=cnt;i++)
{
if(d[tmp[i]]<=mid)add(tmp[i],);
else q[tmp[i]]-=qur(n)-qur(tmp[i]);
}
for(int i=;i<=cnt;i++)if(d[tmp[i]]<=mid)add(tmp[i],-);
for(int i=cnt;i>=;i--)
{
if(d[tmp[i]]<=mid)add(tmp[i],);
else q[tmp[i]]-=qur(tmp[i]);
}
for(int i=;i<=cnt;i++)if(d[tmp[i]]<=mid)add(tmp[i],-);
solve(l,mid);solve(mid+,r);
return ;
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=;i<=n;i++)scanf("%lld",&a[i]),p[a[i]]=i;
for(int i=;i<=m;i++)scanf("%lld",&b[i]),d[b[i]]=i;
for(int i=;i<=n;i++)
{
int tp=qur(n)-qur(a[i]);
ans[]+=tp;
q[a[i]]+=tp;
add(a[i],);
}
memset(c,,sizeof(c));
for(int i=n;i>=;i--)
{
int tp=qur(a[i]);
q[a[i]]+=tp;
add(a[i],);
}
memset(c,,sizeof(c));
solve(,m);
for(int i=;i<m;i++)ans[i]=ans[i-]-q[b[i]];
for(int i=;i<m;i++)printf("%lld\n",ans[i]);
return ;
}