首页 > 代码库 > 【bzoj3295】 Cqoi2011—动态逆序对

【bzoj3295】 Cqoi2011—动态逆序对

2024-08-17 21:07:36   223人阅读

http://www.lydsy.com/JudgeOnline/problem.php?id=3295 (题目链接)

题意

　　给出某种排列，按照某种顺序依次删除m个数，在每次删除一个数前统计序列中逆序对对个数。

Solution

　　作为一个CDQ分治的初学者，我毫不犹豫的%了LCF的题解。

　　这里介绍下三维偏序的求法：一维排序，二维归并，三维树状数组。

　　排序维护x维之后，递归处理：

　　　　1.在处理区间[L,R]的时候，先二分区间[L, (L+R)/ 2]，递归求这个左区间（二分的原因是我在维护y维的时候难免破坏x维的性质，但是二分之后我还是可以保证左区间的x全都大于右区间的x）。

　　　　2.这个时候左区间y维已经有序，我们只好把右区间[(L+R)/2，R]，快排一遍，进行归并式的dp转移（左区间一个指针，右区间一个指针，保证左区间指针所扫过的y一定小于右区间指针所扫过的y），然后在用常规的树状数组维护z。

　　　　3.当然，最后还应该把右区间[(L+R)/2，R]按x快排回去，并递归处理这一段。

　　　　4.最后归并或者快排维护整个区间的y有序。

细节

　　sort一定要注意下标的位置。

代码

// bzoj3295#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define MOD 100000000#define inf 2147483640#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=100010;struct data {int x,y,z;}a[maxn];int n,m,pos[maxn];LL c[maxn],f[maxn];bool cmpx(data a,data b) {return a.x<b.x;}bool cmpy(data a,data b) {return a.y<b.y;}bool cmpz(data a,data b) {return a.z>b.z;}int lowbit(int x) {return -x&x;}LL query(int x) {int res=0;for (int i=x;i;i-=lowbit(i)) res+=c[i];return res;}void add(int x,int val) {for (int i=x;i<=n;i+=lowbit(i)) c[i]+=val;}void clear(int x) {for (int i=x;i<=n;i+=lowbit(i)) c[i]=0;}void solve(int l,int r) {	if (l>=r) return;	int mid=(l+r)>>1;	solve(l,mid);solve(mid+1,r);	sort(a+l,a+mid+1,cmpx);	sort(a+mid+1,a+r+1,cmpx);	for (int i=mid,j=r;j>mid;j--) {		while (i>=l && a[i].x>a[j].x) add(a[i--].y,1);		f[a[j].z]+=query(a[j].y-1);	}	for (int i=l;i<=mid;i++) clear(a[i].y);	for (int i=l,j=mid+1;j<=r;j++) {		while (i<=mid && a[i].x<a[j].x) add(a[i++].y,1);		f[a[j].z]+=query(n)-query(a[j].y);	}	for (int i=l;i<=mid;i++) clear(a[i].y);}int main() {	scanf("%d%d",&n,&m);	for (int x,i=1;i<=n;i++) {		scanf("%d",&x);		pos[x]=i;	}	for (int x,i=1;i<=m;i++) {		scanf("%d",&x);		a[pos[x]]=(data){x,pos[x],i};	}	for (int x=m,i=1;i<=n;i++)		if (a[pos[i]].z==0) a[pos[i]]=(data){i,pos[i],++x};	sort(a+1,a+1+n,cmpz);	solve(1,n);	LL ans=0;	for (int i=1;i<=n;i++) ans+=f[i];	for (int i=1;i<=m;i++) {		printf("%lld\n",ans);		ans-=f[i];	}	return 0;}

　　

【bzoj3295】 Cqoi2011—动态逆序对


联系
我们