记录编号	147125	评测结果	AAAAAAAAAA
题目名称	[CQOI2011]动态逆序对	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	6.007 s
提交时间	2015-01-24 20:10:09	内存使用	105.34 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#define l(x) ch[x][0]
#define r(x) ch[x][1]
#define lb(x) ((x)&(-x))
#define LL unsigned long long
#define Maxn 200010
using namespace std;
int n,m,tot=0,ch[10000010][2]={0},root[Maxn]={0},pos[Maxn],a[Maxn];
int sumt[10000010]={0};
LL ans=0;
inline void qread(int &x){
	char cha;
	while(cha=getchar()) if(isdigit(cha)) break;
	x=cha-'0';
	while(cha=getchar()){
		if(!isdigit(cha)) break;
		x=10*x+cha-'0';
	}
}
inline void insert3(int &o,int qx,int v){
	if(!o) o=++tot;
	int l=1,r=n,now=o;
	while(1){
		sumt[now]+=v;
		if(l==r) break;
		int mid=(l+r)>>1;
		if(qx<=mid){
			r=mid; if(!l(now)) l(now)=++tot;
			now=l(now);
		}
		else{
			l=mid+1; if(!r(now)) r(now)=++tot;
			now=r(now);
		}
	}
}
int query2(int o,int l,int r,int ql,int qr){
	if(!o) return 0;
	if(ql<=l&&r<=qr) return sumt[o];
	int mid=(l+r)>>1,res=0;
	if(ql<=mid) res+=query2(l(o),l,mid,ql,qr);
	if(mid<qr) res+=query2(r(o),mid+1,r,ql,qr);
	return res;
}
void insert1(int x,int y,int v){
	for(int i=x;i<=n;i+=lb(i)) insert3(root[i],y,v);//insert2(root[i],1,n,y,v);
}
int query1(int x,int y,int L,int R){
	int res=0;
	for(int i=y;i>0;i-=lb(i)) res+=query2(root[i],1,n,L,R);
	for(int i=x-1;i>0;i-=lb(i)) res-=query2(root[i],1,n,L,R);
	return res;
}
void remove(int x){
	if(x<n) ans-=query1(x+1,n,1,a[x]);
	if(x>1) ans-=query1(1,x-1,a[x],n);
	insert1(x,a[x],-1);
}
int main(){
	freopen("inverse.in","r",stdin);
	freopen("inverse.out","w",stdout);
	qread(n); qread(m);
	for(int i=1;i<=n;i++){
		qread(a[i]); pos[a[i]]=i;
		insert1(i,a[i],1);
	}
	for(int i=1;i<n;i++) ans+=query1(i+1,n,1,a[i]);
	for(int i=1,x;i<=m;i++){
		qread(x);
		printf("%llu\n",ans); remove(pos[x]);
	}
	return 0;
}