记录编号	460814	评测结果	AAAAAAAAAA
题目名称	[CQOI2011]动态逆序对	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	6.557 s
提交时间	2017-10-18 16:13:21	内存使用	2.22 MiB

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <ctime>
#include <map>
using namespace std;
//#define int long long
inline int read(){
	int sum(0);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
#define get_size(x) (x?x->size:0)
struct node{
	node *lch,*rch;
	int key,fix,size;
	node(int x=0):lch(NULL),rch(NULL),size(1),key(x),fix(rand()){}
	inline void pushup(){
		this->size=get_size(this->lch)+get_size(this->rch)+1;
	}
}*tr[400005];
inline void left_rotate(node *&x){
	node *tmp(x->rch);
	x->rch=tmp->lch;
	tmp->lch=x;
	x->pushup();
	tmp->pushup();
	x=tmp;
}
inline void right_rotate(node *&x){
	node *tmp(x->lch);
	x->lch=tmp->rch;
	tmp->rch=x;
	x->pushup();
	tmp->pushup();
	x=tmp;
}
inline void insert(node *&x,int v){
	if(!x){
		x=new node(v);
		return;
	}
	if(v<=x->key){
		insert(x->lch,v);
		x->pushup();
		if(x->lch->fix<x->fix)
			right_rotate(x);
	}
	else{
		insert(x->rch,v);
		x->pushup();
		if(x->rch->fix<x->fix)
			left_rotate(x);
	}
}
inline void del(node *&x,int v){
	if(x->key==v){
		if(x->lch&&x->rch){
			if(x->lch->fix<x->rch->fix){
				right_rotate(x);
				del(x->rch,v);
			}
			else{
				left_rotate(x);
				del(x->lch,v);
			}
		}
		else{
			node *tmp(NULL);
			if(x->lch)tmp=x->lch;
			else tmp=x->rch;
			delete x;
			x=tmp;
		}
	}
	else{
		if(v<=x->key)del(x->lch,v);
		else del(x->rch,v);
	}
	if(x)x->pushup();
}
inline int qmax(node *now,int x){
	int ret(0);
	while(now){
		if(x>=now->key)now=now->rch;
		else ret+=get_size(now->rch)+1,now=now->lch;
	}
	return ret;
}
inline int qmin(node *now,int x){
	int ret(0);
	while(now){
		if(x<=now->key)now=now->lch;
		else ret+=get_size(now->lch)+1,now=now->rch;
	}
	return ret;
}
int n,m;
int a[100005];
map<int,int>ma;
long long ans;
inline void build(int l,int r,int rt){
	for(int i=l;i<=r;++i)insert(tr[rt],a[i]);
	if(l==r)return;
	int mid((l+r)>>1);
	build(l,mid,rt<<1);build(mid+1,r,rt<<1|1);
}
inline int qmax(int ll,int rr,int x,int l,int r,int i){
	if(ll<=l&&r<=rr)return qmax(tr[i],x);
	int mid((l+r)>>1),ret(0);
	if(ll<=mid)ret+=qmax(ll,rr,x,l,mid,i<<1);
	if(mid<rr)ret+=qmax(ll,rr,x,mid+1,r,i<<1|1);
	return ret;
}
inline int qmin(int ll,int rr,int x,int l,int r,int i){
	if(ll<=l&&r<=rr)return qmin(tr[i],x);
	int mid((l+r)>>1),ret(0);
	if(ll<=mid)ret+=qmin(ll,rr,x,l,mid,i<<1);
	if(mid<rr)ret+=qmin(ll,rr,x,mid+1,r,i<<1|1);
	return ret;
}
inline void del(int pos,int i,int l,int r){
	del(tr[i],a[pos]);
	if(l==r)return;
	int mid((l+r)>>1);
	if(pos<=mid)del(pos,i<<1,l,mid);
	else del(pos,i<<1|1,mid+1,r);
}
signed main(){
	freopen("inverse.in","r",stdin);
	freopen("inverse.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;++i)a[i]=read(),ma[a[i]]=i;
	build(1,n,1);
	for(int i=2;i<=n;++i)
		ans+=qmax(1,i-1,a[i],1,n,1);
	printf("%lld\n",ans);
	while(m--){
		if(!m)break;
		int x(read());
		long long tmp(0);
		if(ma[x]!=1)tmp+=qmax(1,ma[x]-1,x,1,n,1);
		if(ma[x]!=n)tmp+=qmin(ma[x]+1,n,x,1,n,1);
		ans-=tmp;
		printf("%lld\n",ans);
		del(ma[x],1,1,n);
	}
}