记录编号	322251	评测结果	AAAAAAAAAA
题目名称	[CQOI2011]动态逆序对	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	0.708 s
提交时间	2016-10-14 20:58:22	内存使用	11.07 MiB

/*
>>>三位偏序(t,x,y)分别表示插入时间，下标和值 
>>>节点(t0,x0,y0)对偏序对个数的影响分为v1和v2两部分 
>>>v1=sum{j(tj<t0&&x<x0&&y>y0)}
>>>v2=sum{j(tj<t0&&x>x0&&y<y0)}
>>>我们按x排序，对t分治，用树状数组维护y 
>>>用倒序处理来将麻烦的删除转变为插入，删除越早，插入越晚 
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
const int maxn=100005,maxm=(50005+maxn)<<1;
struct _q{int t,x,y;}q[maxm],L[maxm],R[maxn];
int n,m,v1[maxn],v2[maxn],pos[maxn];bool del[maxn];
void _in(){
	scanf("%d%d",&n,&m);int i,x,tim=n;
	for(i=1;i<=n;i++)scanf("%d",&q[i].y),pos[q[i].y]=q[i].x=i;
	for(i=1;i<=m;i++)scanf("%d",&x),q[pos[x]].t=tim--;
	for(i=1;i<=n;i++)if(!q[i].t)q[i].t=tim--;
}
#define _low (i&(-i))
int c1[maxn],c2[maxn];LL ans[maxn];
void _addup(int i,int x){
	for(;i<=n;i+=_low)c1[i]+=x;	
}
void _adddown(int i,int x){
	for(;i;i-=_low)c2[i]+=x;	
}
int _getdown(int i){
	int res=0;for(;i;i-=_low)res+=c1[i];return res;
}
int _getup(int i){
	int res=0;for(;i<=n;i+=_low)res+=c2[i];return res;	
}
void _run(int l,int r){
	if(l==r)return;	
	int i,j,mid=(l+r)>>1,cnt1=0,cnt2=0;
	for(i=l;i<=r;i++)
		if(q[i].t<=mid)L[++cnt1]=q[i];
		else R[++cnt2]=q[i];
	for(i=1,j=1;i<=cnt2;i++){//x<x0&&y>y0
		for(;j<=cnt1&&L[j].x<R[i].x;j++)_adddown(L[j].y,1);
		v1[R[i].t]+=_getup(R[i].y+1);
	}
	for(i=1;i<j;i++)_adddown(L[i].y,-1);
	for(i=cnt2,j=cnt1;i;i--){//x>x0&&y<y0
		for(;j&&L[j].x>R[i].x;j--)_addup(L[j].y,1);
		v2[R[i].t]+=_getdown(R[i].y-1);
	}
	for(i=cnt1;i>j;i--)_addup(L[i].y,-1);
	for(i=1;i<=cnt1;i++)q[l+i-1]=L[i];
	for(i=1;i<=cnt2;i++)q[l+cnt1+i-1]=R[i];
	_run(l,mid),_run(mid+1,r);
}
void _work(){
	_in();_run(1,n);
	for(int i=1;i<=n;i++)ans[i]=ans[i-1]+(LL)(v1[i]+v2[i]);
	for(int i=n;i>=n-m+1;i--)printf("%lld\n",ans[i]);
}
int main(){
#define _Rabit _RABIT
#ifdef _Rabit
	freopen("inverse.in","r",stdin);
	freopen("inverse.out","w",stdout);
#endif
	_work();
#ifndef _Rabit
	getchar(),getchar();
#endif
	fclose(stdin);fclose(stdout);
}