记录编号	256278	评测结果	AAAAAAAAEE
题目名称	[CQOI2011]动态逆序对	最终得分	80
用户昵称	jiazihankk	是否通过	未通过
代码语言	C++	运行时间	5.143 s
提交时间	2016-04-29 20:08:44	内存使用	119.33 MiB

#include<bits/stdc++.h>
#define rep(i,k,n) for(int i=k;i<=(n);i++)
#define rep2(i,k,n) for(int i=k;i>=(n);i--)
#define ls ch[x][0]
#define rs ch[x][1]
using namespace std;
const int N=300005;
const int M=10000005;
typedef long long ll;
int n,m,a[N],pos[N];
int tr[N];
void ad(int x,int d){for(;x<=n;x+=(x&-x))tr[x]+=d;}
int Q(int x){int res=0;for(;x;x-=(x&-x))res+=tr[x];return res;}
int rt[N],sum[M],ch[M][2],tot=0;
inline void up(int x,int l,int r){if(l==r)return;
	sum[x]=sum[ls]+sum[rs];
}
void insert(int& x,int l,int r,int v,int d){
	if(!x)x=++tot;
	if(l==r){sum[x]+=d;return;}
	int mid=(l+r)>>1;
	if(v<=mid)insert(ls,l,mid,v,d);
	else insert(rs,mid+1,r,v,d);
	up(x,l,r);
}
void ins(int x,int l,int r,int v,int d){
	if(l==r){insert(rt[x],1,n,pos[v],d);return;}
	insert(rt[x],1,n,pos[v],d);
	int mid=(l+r)>>1;
	if(v<=mid)ins(x<<1,l,mid,v,d);
	else ins(x<<1|1,mid+1,r,v,d);
}
int query(int x,int l,int r,int v){
	if(r<=v)return sum[x];
	int mid=(l+r)>>1;
	if(v<=mid)return query(ls,l,mid,v);
	else return sum[ls]+query(rs,mid+1,r,v);
}
inline int get(int x,int l,int r,int v){if(l>r)return 0;
    if(r<=v){return query(rt[x],1,n,pos[v]);}
    else{
    	int mid=(l+r)>>1;
    	if(v<=mid)return get(x<<1,l,mid,v);
    	else{
    	 return query(rt[x<<1],1,n,pos[v])+get(x<<1|1,mid+1,r,v);
        }
    }
}
int main(){
//freopen("in.in","r",stdin);
//freopen("out.out","w",stdout);
freopen("inverse.in","r",stdin);
freopen("inverse.out","w",stdout);
	scanf("%d%d",&n,&m);
	rep(i,1,n){
	scanf("%d",&a[i]);
	pos[a[i]]=i;
	}
	ll ans=0;rep2(i,n,1){ans+=Q(a[i]);ad(a[i],1);}
	int x;
	rep(i,1,n)ins(1,1,n,a[i],1);
	rep(i,1,m){
		printf("%lld\n",ans);
		scanf("%d",&x);
		ins(1,1,n,x,-1);
		ad(x,-1);
		int num=query(rt[1],1,n,pos[x]);
		int tmp=get(1,1,n,x);
		int Sum=Q(x);
		ans-=Sum-tmp;
		ans-=num-tmp;
	}
	return 0;
}