记录编号	222015	评测结果	AAAAAAAAAA
题目名称	[CQOI2011]动态逆序对	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	4.384 s
提交时间	2016-01-27 20:15:38	内存使用	98.79 MiB

#define MAXN 100010UL
#define MAXQ 2000000UL
#define LL long long

#include<cstdio>
#include<algorithm>

using namespace std;

int n,m,seq[MAXN],tot;
LL tree[MAXN],Ans[MAXN];
int pos[MAXN],del[MAXN];

struct AskCnt{
	bool typ;LL val;
	int x,y,id,ti;
}Ask[MAXQ],tmp[MAXQ];

bool cmp(const AskCnt & a,const AskCnt & b)
{
    if(a.x==b.x&&a.y==b.y)return a.typ<b.typ;
	return a.x==b.x?a.y<b.y:a.x<b.x;
}

inline void Add(int x,LL w)
{
	for(int i=x;i<=n;i+=(i&(-i)))
	    tree[i]+=w;
}

inline LL Query(int x)
{
	LL tans=0;
	for(int i=x;i>0;i-=(i&(-i)))
		tans+=tree[i];
	return tans;
}

inline void Add_ask(int x1,int y1,int x2,int y2,int tim)
{
	tot++;Ask[tot].x=x2;Ask[tot].y=y2;Ask[tot].ti=tim;Ask[tot].typ=true;Ask[tot].id=tot;Ask[tot].val=1;
	tot++;Ask[tot].x=x2;Ask[tot].y=y1-1;Ask[tot].ti=tim;Ask[tot].typ=true;Ask[tot].id=tot;Ask[tot].val=-1;
	tot++;Ask[tot].x=x1-1;Ask[tot].y=y2;Ask[tot].ti=tim;Ask[tot].typ=true;Ask[tot].id=tot;Ask[tot].val=-1;
	tot++;Ask[tot].x=x1-1;Ask[tot].y=y1-1;Ask[tot].ti=tim;Ask[tot].typ=true;Ask[tot].id=tot;Ask[tot].val=1;
}

inline void Add_add(int x,int y,int w)
{
	tot++;Ask[tot].x=x;Ask[tot].y=y;Ask[tot].typ=false;Ask[tot].id=tot;Ask[tot].val=1;
}

inline void Add_num(int x,int y,int tim)
{
	Add_ask(1,y,x,n,tim);
	Add_ask(x,1,n,y,tim);
	Add_add(x,y,1);
}

inline void CDQ(int l,int r)
{
	if(l==r)return;
	int mid=(l+r)>>1;
	int l1=l-1,l2=mid;
	for(int i=l;i<=r;i++){
		if(Ask[i].id<=mid&&(!Ask[i].typ))Add(Ask[i].y,Ask[i].val);
		if(Ask[i].id>mid&&(Ask[i].typ))Ans[Ask[i].ti]+=Ask[i].val*Query(Ask[i].y);
	}
	for(int i=l;i<=r;i++)
		if(Ask[i].id<=mid&&(!Ask[i].typ))Add(Ask[i].y,-Ask[i].val);
	for(int i=l;i<=r;i++){
		if(Ask[i].id<=mid)tmp[++l1]=Ask[i];
		else tmp[++l2]=Ask[i];
	}
	for(int i=l;i<=r;i++)Ask[i]=tmp[i];
	CDQ(l,mid);CDQ(mid+1,r);
}

int main()
{
    freopen("inverse.in","r",stdin);
	freopen("inverse.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&seq[i]);
		pos[seq[i]]=i;
	}
	for(int i=1;i<=m;i++){
		scanf("%d",&del[i]);
		seq[pos[del[i]]]=0;
	}
	for(int i=1;i<=n;i++)
	    if(seq[i])Add_num(i,seq[i],0);
	for(int i=m;i>=1;i--)
		Add_num(pos[del[i]],del[i],i);
	sort(Ask+1,Ask+tot+1,cmp);
	CDQ(1,tot);
	Ans[m]+=Ans[0];
	for(int i=m-1;i>=1;i--)Ans[i]+=Ans[i+1];
	for(int i=1;i<=m;i++)printf("%lld\n",Ans[i]);
}