【题解】[CQOI]动态逆序对

题目链接

题意如题，维护一个动态序列的逆序对总数。

注意题目给的是\([1,n]\)的排列，所以没必要离散化了。

考虑逆序对：二维偏序可以用树状数组做，现在是三维偏序，即加了一个时间维度。

找一个数前面大于它的数和后面小于它的数，可以想到主席树做。

考虑修改操作，普通主席树的修改是不好做的，在静态前缀和上面修改太累了。

考虑树状数组套动态开点权值线段树。

树状数组维护前缀和即可。

注意的是，修改操作不能只把删的这个值的前后逆序对数减掉，因为这会影响后面数的逆序对个数。所以要在主席树（或者说动态开点权值线段树）上面动态修改，维护正确信息。

#include<bits/stdc++.h>

using namespace std;

const int MAXN=4e5+10;

typedef long long ll;

#define rg register

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch>='0'&&ch<='9'){

		s=(s<<1)+(s<<3)+(ch^48);

		ch=getchar();

	}

	return w==-1?-s:s;

}

int a[MAXN],n,m,b[MAXN];

int cur,num[MAXN];

ll res1[MAXN],res2[MAXN];

ll Ans;

namespace SGT{

	int rt[MAXN<<2],tot,lc[MAXN<<5],rc[MAXN<<5],sum[MAXN<<5];

	void build(int &x){x=++tot;}

	void update(int &x,int l,int r,int pos,int v){

		if(!x)build(x);

		sum[x]+=v;

		if(l==r)return;

		int mid=l+r>>1;

		if(pos<=mid)update(lc[x],l,mid,pos,v);

		else update(rc[x],mid+1,r,pos,v);

	}

}

using namespace SGT;

inline int lowbit(int x){return x&(-x);}

void upd(int x,int pos,int v){for(;x<=n;x+=lowbit(x))update(rt[x],1,n,pos,v);}

int query1(int r,int x){

	int ans=0;

	for(rg int i=r;i;i-=lowbit(i)){

		int L=1,R=n;

		int u=rt[i];

		while(sum[u]&&(L^R)){

			rg int mid=L+R>>1;mid++;

			if(mid>x)ans+=sum[rc[u]],u=lc[u],R=mid-1;

			else L=mid,u=rc[u];

		}

	}

	return ans;

}

int query2(int l,int x){

	int ans=0;

	for(rg int i=l-1;i;i-=lowbit(i)){

		int L=1,R=n,u=rt[i];

		while(sum[u]&&(L^R)){

			rg int mid=L+R>>1;

			if(mid<x)ans-=sum[lc[u]],u=rc[u],L=mid+1;

			else u=lc[u],R=mid;

		}

	}

	for(rg int i=n;i;i-=lowbit(i)){

		int L=1,R=n,u=rt[i];

		while(sum[u]&&(L^R)){

			rg int mid=L+R>>1;

			if(mid<x)ans+=sum[lc[u]],u=rc[u],L=mid+1;

			else u=lc[u],R=mid;

		}

	}

	return ans;

}

int main(){

	n=read(),m=read();

	for(rg int i=1;i<=n;++i)a[i]=read(),num[a[i]]=i;

	for(rg int i=1;i<=m;++i)b[i]=read();

	for(rg int i=1;i<=n;++i)upd(i,a[i],1);

	for(rg int i=1;i<=n;++i){

		res1[i]=query1(i-1,a[i]);

		res2[i]=query2(i+1,a[i]);

		Ans+=res1[i]+res2[i];

	}

	Ans>>=1;

	printf("%lld\n",Ans);

	for(rg int i=1;i<m;++i){

		upd(num[b[i]],b[i],-1);

		Ans-=query1(num[b[i]]-1,b[i]);

		Ans-=query2(num[b[i]]+1,b[i]);

		printf("%lld\n",Ans);

	}

	return 0;

}

巴特西

【题解】[CQOI]动态逆序对

最新文章

热门文章