夕阳一片红求调

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e5+5;
const int INF=1e9+7;
int n,m,a[N];
struct FHQ{
	int ls,rs,key,prio,siz;
}t[10000005];
int tot;
struct FHQ_Treap{
	int root;
	inline int Newnode(int x){
		t[++tot].ls=t[tot].rs=0;
		t[tot].key=x;t[tot].prio=rand();
		t[tot].siz=1;
		return tot;
	}
	inline void pushup(int x){
		t[x].siz=t[t[x].ls].siz+t[t[x].rs].siz+1;
	}
	void split(int u,int x,int &l,int &r){
		if(u==0){
			l=r=0;return;
		}
		if(t[u].key<=x) l=u,split(t[u].rs,x,t[u].rs,r);
		else r=u,split(t[u].ls,x,l,t[u].ls);
		pushup(u);
	}
	int merge(int l,int r){
		if(l==0||r==0) return l+r;
		if(t[l].prio>t[r].prio){
			t[l].rs=merge(t[l].rs,r);
			pushup(l);return l;
		}else{
			t[r].ls=merge(l,t[r].ls);
			pushup(r);return r; 
		}
	}
	void Insert(int x){
		int l,r;
		split(root,x,l,r);
		root=merge(l,merge(Newnode(x),r));
	}
	void Build(int l,int r){
		for(int i=l;i<=r;i++) Insert(a[i]);
	}
	void Delete(int x){
		int l,r,p;
		split(root,x,l,r);
		split(l,x-1,l,p);
		root=merge(l,merge(merge(t[p].ls,t[p].rs),r));
	}
	int prerank(int x){
		int l,r,inf;
		split(root,INF-1,l,inf);
		split(l,x,l,r);
		int ranking=t[r].siz;
		root=merge(l,merge(r,inf));
		return ranking;
	}
	int nextrank(int x){
		int l,r,inf;
		split(root,INF-1,l,inf);
		split(l,x-1,l,r);
		int ranking=t[l].siz;
		root=merge(l,merge(r,inf));
		return ranking;
	}
}fhq[N<<2];
#define mid (l+r>>1)
struct segement{
	void build(int l,int r,int k){
		fhq[k].Build(l,r);
		if(l==r) return;
		build(l,mid,k<<1);build(mid+1,r,k<<1|1);
	}
	void change(int l,int r,int k,int z,int v){
		fhq[k].Delete(a[z]);
		fhq[k].Insert(v);
		if(l==r) return;
		if(z<=mid) change(l,mid,k<<1,z,v);
		else change(mid+1,r,k<<1|1,z,v);
	}
	LL getrank1(int l,int r,int k,int ll,int rr,int v){
		if(r<ll||l>rr) return 0ll;
		if(ll<=l&&r<=rr) return (LL)fhq[k].prerank(v);
		LL res=0;
		if(ll<=mid) res+=getrank1(l,mid,k<<1,ll,rr,v);
		if(rr>mid) res+=getrank1(mid+1,r,k<<1|1,ll,rr,v);
		return res;
	}
	LL getrank2(int l,int r,int k,int ll,int rr,int v){
		if(r<ll||l>rr) return 0ll;
		if(ll<=l&&r<=rr) return (LL)fhq[k].nextrank(v);
		LL res=0;
		if(ll<=mid) res+=getrank2(l,mid,k<<1,ll,rr,v);
		if(rr>mid) res+=getrank2(mid+1,r,k<<1|1,ll,rr,v);
		return res;
	}
}T;
int id[N],s;
int temp[N],r[N];
LL ans=0;
void msort(int s,int t){
	if(s==t) return ;
	int Mid=s+t>>1;
	msort(s,Mid),msort(Mid+1,t);
	int i=s,j=Mid+1,k=s;
	while(i<=Mid&&j<=t)
		if(temp[i]<=temp[j]) r[k++]=temp[i++];
		else r[k++]=temp[j++],ans+=(LL)Mid-i+1;
	while(i<=Mid) r[k]=temp[i],k++,i++;
	while(j<=t) r[k]=temp[j],k++,j++;
	for(int i=s;i<=t;i++) temp[i]=r[i];
}
int main(){
//	freopen("P3157_1.in","r",stdin);
//	freopen("P3157_my.out","w",stdout);
	srand(time(NULL));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),id[a[i]]=i,temp[i]=a[i];
	T.build(1,n,1);
	msort(1,n);
	for(int i=1;i<=m;i++){
		printf("%lld\n",ans);
		scanf("%d",&s);
		if(i==m) break;
		ans-=(T.getrank1(1,n,1,1,id[s]-1,s)+T.getrank2(1,n,1,id[s]+1,n,s));
		T.change(1,n,1,id[s],INF);
		a[id[s]]=INF;
	}
	return 0;
}