记录编号	123596	评测结果	AAAAAAAAAA
题目名称	[CQOI2011]动态逆序对	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	3.527 s
提交时间	2014-09-28 12:00:35	内存使用	116.67 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
const int MAXN=1e5+10;
typedef long long LL;
int N;
struct SegTree{
	int ls[MAXN*100],rs[MAXN*100],sz[MAXN*100];
	int Root[MAXN];
	int node_cnt;
	SegTree(){ node_cnt=1; }
	void insert(int & root,int left,int right,int pos,int val){
		if(!root) root=node_cnt++;
		sz[root]+=val;
		if(left==right)return;
		int mid=(left+right)>>1;
		if(pos<=mid) insert(ls[root],left,mid,pos,val);
		else insert(rs[root],mid+1,right,pos,val);
	}		
	void insert(int pos,int num){
		for(;pos<=N;pos+=pos&-pos){
			insert(Root[pos],1,N,num,1);
		}
	}
	void remove(int pos,int num){
		for(;pos<=N;pos+=pos&-pos){
			insert(Root[pos],1,N,num,-1);
		}
	}
	int IncRt[MAXN],DecRt[MAXN];
	int query_great(int x,int y,int num){
		LL ret=0;
		IncRt[0]=DecRt[0]=0;
		for(int i=y;i;i-=i&-i) IncRt[ ++IncRt[0] ]=Root[i];
		for(int i=x-1;i;i-=i&-i) DecRt[ ++DecRt[0] ]=Root[i];
		int left=1,right=N;
		while(true){
			if(left==right){
				if(left==num){
					for(int i=1;i<=IncRt[0];i++) ret+=sz[ IncRt[i] ];
					for(int i=1;i<=DecRt[0];i++) ret-=sz[ DecRt[i] ];
				}
				break;
			}
			int mid=(left+right)>>1;
			if(num<=mid){
				for(int i=1;i<=IncRt[0];i++) ret+=sz[rs[IncRt[i]]];
				for(int i=1;i<=DecRt[0];i++) ret-=sz[rs[DecRt[i]]];
				for(int i=1;i<=IncRt[0];i++) IncRt[i]=ls[IncRt[i]];
				for(int i=1;i<=DecRt[0];i++) DecRt[i]=ls[DecRt[i]];
				right=mid;
			}else{
				for(int i=1;i<=IncRt[0];i++) IncRt[i]=rs[IncRt[i]];
				for(int i=1;i<=DecRt[0];i++) DecRt[i]=rs[DecRt[i]];
				left=mid+1;
			}
		}
		return ret;
	}
	int query_less(int x,int y,int num){
		LL ret=0;
		IncRt[0]=DecRt[0]=0;
		for(int i=y;i;i-=i&-i) IncRt[ ++IncRt[0] ]=Root[i];
		for(int i=x-1;i;i-=i&-i) DecRt[ ++DecRt[0] ]=Root[i];
		int left=1,right=N;
		while(true){
			if(left==right){
				if(left==num){
					for(int i=1;i<=IncRt[0];i++) ret+=sz[ IncRt[i] ];
					for(int i=1;i<=DecRt[0];i++) ret-=sz[ DecRt[i] ];
				}
				break;
			}
			int mid=(left+right)>>1;
			if(num<=mid){
				for(int i=1;i<=IncRt[0];i++) IncRt[i]=ls[IncRt[i]];
				for(int i=1;i<=DecRt[0];i++) DecRt[i]=ls[DecRt[i]];
				right=mid;
			}else{
				for(int i=1;i<=IncRt[0];i++) ret+=sz[ls[IncRt[i]]];
				for(int i=1;i<=DecRt[0];i++) ret-=sz[ls[DecRt[i]]];
				for(int i=1;i<=IncRt[0];i++) IncRt[i]=rs[IncRt[i]];
				for(int i=1;i<=DecRt[0];i++) DecRt[i]=rs[DecRt[i]];
				left=mid+1;
			}
		}
		return ret;
	}
}ST;

int Num[MAXN],Pos[MAXN],M;
LL TOT;
void init(){
	scanf("%d %d",&N,&M);
	for(int i=1;i<=N;i++){
		int num;scanf("%d",&num);
		Num[i]=num;
		Pos[num]=i;
		
		ST.insert(i,num);
		TOT+=ST.query_great(1,i,num+1);
	}
}

void work(){
	for(int i=1;i<=M;i++){
		//cout<<TOT<<endl;
		printf("%lld\n",TOT);
		int num;scanf("%d",&num);
		int qian=ST.query_great(1,Pos[num],num+1);
		int hou=ST.query_less(Pos[num],N,num-1);
		TOT-=qian+hou;
		ST.remove(Pos[num],num);
	}
}

int main(){
	freopen("inverse.in","r",stdin);//ܳ ܳܳܳܳܳܳܳܳܳܳܳܳܳܳܳܳܳܳܳܳܳܳܳܳܳܳܳ
	freopen("inverse.out","w",stdout);
	init();
	work();
	return 0;
}