题目链接：
(Wa)毒瘤数据结构为什么卡常啊。。
首先，对于刚开始的逆序对数很好求，树状数组/归并排序都行。
对于删除一个数，如果左边有(a)个数比它大，右边有(b)个比它小，那么就是减去了((a+b))个逆序对。
那么对于这种问题，可以用树状数组套线段树解决。
树状数组的每个区间是一颗权值线段树。
那么这个问题就愉快的解决了。。。吗？
线段树内存会炸，要改成动态开点。
然后就是卡常，实在不行加快读什么的O2也行
注意(UVA)的数据大一倍
//Luogu要开O2，不然会T(x
#include <cstdio>
#include <cstring>
typedef long long ll;
int n,m;
int a[200005],Pos[200005],Ql[200005],Qr[200005];
int Root[200005],Node[10000005],Ls[10000005],Rs[10000005],Cnt;
//UVA上节点数要开大一倍
void Modify(int &p,int l,int r,int v,int c)//新增c个v值
{
if(!p)p=++Cnt;
Node[p]+=c;
if(l==r)return;
int Mid=(l+r)>>1;
if(v<=Mid)Modify(Ls[p],l,Mid,v,c);
else Modify(Rs[p],Mid+1,r,v,c);
}
int Query(int l,int r,int x,int Mode)//查询[l,r]内比x 大/小(Mode=0/1) 的数的个数
{
int Qlc=0,Qrc=0,Sum=0;
for(int i=l-1;i;i^=i&-i)Ql[++Qlc]=Root[i];//[1,l-1]对应的区间根节点
for(int i=r;i;i^=i&-i)Qr[++Qrc]=Root[i];
for(l=1,r=n;l<r;)
{
int Mid=(l+r)>>1;
if(x>Mid)
{
if(Mode)
{
for(int i=1;i<=Qlc;++i)Sum-=Node[Ls[Ql[i]]];
for(int i=1;i<=Qrc;++i)Sum+=Node[Ls[Qr[i]]];//此区间完全选中，直接统计
}
for(int i=1;i<=Qlc;++i)Ql[i]=Rs[Ql[i]];
for(int i=1;i<=Qrc;++i)Qr[i]=Rs[Qr[i]];
l=Mid+1;//转移区间
}
else
{
if(!Mode)
{
for(int i=1;i<=Qlc;++i)Sum-=Node[Rs[Ql[i]]];
for(int i=1;i<=Qrc;++i)Sum+=Node[Rs[Qr[i]]];
}
for(int i=1;i<=Qlc;++i)Ql[i]=Ls[Ql[i]];
for(int i=1;i<=Qrc;++i)Qr[i]=Ls[Qr[i]];
r=Mid;
}
}
return Sum;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
long long Ans=0;
memset(Root,0,sizeof Root);
memset(Node,0,sizeof Node);
memset(Ls,0,sizeof Ls);
memset(Rs,0,sizeof Rs);
Cnt=0;//在Luogu/BZOJ上可以去掉初始化，卡常
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]),Pos[a[i]]=i;
Ans+=Query(1,i-1,a[i],0);
for(int j=i;j<=n;j+=j&-j)
Modify(Root[j],1,n,a[i],1);//类似的BIT修改
}
for(int x;m--;)
{
printf("%lld
",Ans);
scanf("%d",&x);
Ans-=Query(1,Pos[x]-1,x,0);
Ans-=Query(Pos[x]+1,n,x,1);
for(int j=Pos[x];j<=n;j+=j&-j)
Modify(Root[j],1,n,x,-1);
}
}
return 0;
}