//鸣谢 litble(kb)Dalao 细心地为我讲解 cdq 分治与这道题，感激不尽啊 QvQ

# 2. 题解

• 插入时间 $t$
• 插入在原序列中的位置 $x$
• 插入的值 $y$

#include <bits/stdc++.h>
#define lowbit(a) (a&-a)
#define NS (100005)
using namespace std;
typedef long long LL;
template<typename _Tp>inline void IN(_Tp&dig)
{
char c;bool flag=0;dig=0;
while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
struct query{LL t,x,y,ans;}Q[NS],t1[NS],t2[NS];
LL n,m,num[NS],h[NS],del[NS],cnt,t[NS];
bool book[NS];
void binary(LL l,LL r)
{
if(l==r)return;
LL mid=(l+r)>>1;
binary(l,mid),binary(mid+1,r);
for(LL i=l;i<=mid;i++)t1[i]=Q[i];
for(LL i=mid+1;i<=r;i++)t2[i]=Q[i];
t1[mid+1].x=t2[r+1].x=INT_MAX;
for(LL i=l,x1=l,x2=mid+1;i<=r;i++)
if(t1[x1].x<t2[x2].x)Q[i]=t1[x1++];
else Q[i]=t2[x2++];
for(LL i=l,tot=0;i<=r;i++)
else Q[i].ans+=tot-sum(Q[i].y-1);
for(LL i=r;i>=l;i--)
else Q[i].ans+=sum(Q[i].y-1);
}
inline bool cmp(query a,query b){return a.t<b.t;}
int main()
{
IN(n),IN(m);
for(LL i=1;i<=n;i++)IN(num[i]),h[num[i]]=i;
for(LL i=1;i<=m;i++)IN(del[i]),book[h[del[i]]]=1;
for(LL i=1;i<=n;i++)if(!book[i])Q[++cnt]=(query){cnt,i,num[i],0};
for(LL i=m;i>=1;i--)Q[++cnt]=(query){cnt,h[del[i]],del[i],0};
binary(1,cnt),sort(Q+1,Q+1+cnt,cmp);
for(LL i=2;i<=cnt;i++)Q[i].ans+=Q[i-1].ans;
for(LL i=cnt;i>cnt-m;i--)printf("%lld\n",Q[i].ans);
return 0;
}