P3157

MnZn用的树状数组套权值线段树

并且把删除元素变成了逆序添加元素并计算贡献

样例没过，代码如下：

#include<cstdio>
const int M=1e5+10,MAXN=1e5;

struct node{
	int lc,rc,val;
}tr[M*400];
int cntv;
void pushup(int k){
	tr[k].val=tr[tr[k].lc].val+tr[tr[k].rc].val;
}
void update(int &k,int l,int r,int pos,int val){
	if(!k) k=++cntv;
	if(l==r) return tr[k].val+=val,void();
	int mid=(l+r)>>1;
	if(pos<=mid) update(tr[k].lc,l,mid,pos,val);
	else update(tr[k].rc,mid+1,r,pos,val);
	pushup(k);
}

int n,m,a[M],ans[M],pos[M],del[M];
int lowbit(int x){
	return x&-x;
}
int rt[M];
void add(int pos1,int pos2,int val){
	for(int i=pos1;i<=n;i+=lowbit(i)) update(rt[i],1,n,pos2,val);
}

int tmp1[M],tmp2[M];
int query_sum(int L,int R,int l,int r,int *lrt,int *rrt){
	if(L<=l and r<=R){
		int res=0;
		for(int i=1;i<=rrt[0];i++) res+=tr[rrt[i]].val;
		for(int i=1;i<=lrt[0];i++) res-=tr[lrt[i]].val;
		return res;
	}
	int mid=(l+r)>>1,sum=0;
	tmp1[0]=lrt[0],tmp2[0]=rrt[0];
	if(L<=mid){
		for(int i=1;i<=lrt[0];i++) tmp1[i]=tr[lrt[i]].lc;
		for(int i=1;i<=rrt[0];i++) tmp2[i]=tr[rrt[i]].lc;
		sum+=query_sum(L,R,l,mid,tmp1,tmp2);
	}
	if(R>mid){
		for(int i=1;i<=lrt[0];i++) tmp1[i]=tr[lrt[i]].rc;
		for(int i=1;i<=rrt[0];i++) tmp2[i]=tr[rrt[i]].rc;
		sum+=query_sum(L,R,mid+1,r,tmp1,tmp2);
	}
	return sum;
}
int lrt[M],rrt[M];
int query(int l1,int r1,int l2,int r2){
	lrt[0]=rrt[0]=0;
	for(int i=l1-1;i;i-=lowbit(i)) lrt[++lrt[0]]=rt[i];
	for(int i=r1;  i;i-=lowbit(i)) rrt[++rrt[0]]=rt[i];
	return query_sum(l2,r2,1,n,lrt,rrt);
}

bool mark[M];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),pos[a[i]]=i;
	for(int i=1;i<=m;i++) scanf("%d",&del[i]),mark[del[i]]=true;
	for(int i=1;i<=n;i++){
		if(mark[i]) continue;
		ans[0]+=query(1,a[i],pos[a[i]],n);
		ans[0]+=query(a[i],n,1,pos[a[i]]);
		add(a[i],pos[a[i]],1);
	}
	for(int i=m;i>=1;i--){
		int u=query(del[i],n,1,pos[del[i]]),v=query(1,del[i],pos[del[i]],n);
		//u:值处于[del[i],n],位置在[1,pos[del[i]]]的总数
		//v:值处于[1,del[i]],位置在[pos[del[i]],n]的总数 
		//printf("%d %d\n",u,v);
		ans[m-i+1]=ans[m-i]+u+v;
		add(del[i],pos[del[i]],1);
	}
	for(int i=m;i>=1;i--) printf("%d\n",ans[i]);
	return 0;
}