四维偏序 CDQ套CDQ

对CDQ深一步的理解

昨天做了一道CDQ,看了一堆CDQ可做的题,今天又做了一道四维偏序

感觉对CDQ的理解又深了一点,故来写一写现在自己对于CDQ的理解

CDQ其实就是实现了这样的一个问题的转化:

\(a_{l} < a_{l+1} < ... < a_r => (a_l,a_{l+1},...,a_{mid}) \text{都小于} (a_{mid+1},a{mid+2},...,a_r)\)

然后我们就知道这时候左边所有的点都一定小于右边的点

在四维偏序的算法中,那就是左边的点可以对右边的点做出贡献(仅在当前维度下)

这样就强行消除了一个维度的限制.

四维偏序

COGS 2479

题目大意

给定一个有\(n\)个元素的序列，元素编号为\(1~n\)，每个元素有三个属性\(a,b,c\),求序列中满足\(i<j\)且\(a_i<a_j\)且\(b_i<b_j\)且\(c_i<c_j\)的数对\((i,j)\)的个数。

题解

我们把下标也看作一个维度,那么这就是个四维偏序

我们在下标的维度上CDQ

然后记录每个元素在第一次CDQ中是较小的还是较大的.

因为只有较小的元素才能对较大的元素做出贡献

只有较大的元素才能接受较小的元素的影响.

所以我们处理出来后这就变成了一个三维偏序

所以我们在对这个序列(CDQ+扫描线+树状数组)求三维偏序即可

Code

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

inline void read(int &x){

	x=0;char ch;bool flag = false;

	while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;

}

const int maxn = 50010;

struct Node{

	int a,b,c;

	bool is_sm;

	Node(){a=b=c=is_sm = 0;}

}a[maxn],tmp1[maxn],tmp2[maxn];

int c[maxn],n,init_tmp[maxn],ans=0;

#define lowbit(x) (x&-x)

inline void modify(int x,int y){

	for(;x<=n;x+=lowbit(x)) c[x] += y;

}

inline int query(int x){

	int ret = 0;

	for(;x;x-=lowbit(x)) ret += c[x];

	return ret;

}

void solve2(int l,int r){

	if(l == r) return ;

	int mid = l+r >> 1;

	solve2(l,mid);solve2(mid+1,r);

	int i = l,j = mid+1,k = l;

	Node *a = tmp1,*tmp = tmp2;

	init_tmp[0] = 0;

	while(i <= mid || j <= r){

		if((j > r) || (i <= mid && a[i].b < a[j].b)){

			if( a[i].is_sm){

				modify(a[i].c,1);

				init_tmp[++init_tmp[0]] = i;

			}tmp[k++] = a[i++];

		}else{

			if(!a[j].is_sm){

				ans += query(a[j].c);

			}tmp[k++] = a[j++];

		}

	}for(int i = 1;i<=init_tmp[0];++i) modify(a[init_tmp[i]].c,-1);

	copy(tmp+l,tmp+r+1,a+l);

}

void solve1(int l,int r){

	if(l == r) return ;

	int mid = l+r >> 1;

	solve1(l,mid);solve1(mid+1,r);

	int i = l,j = mid+1,k = l;

	Node *tmp = tmp1;

	while(i <= mid || j <= r){

		if((j > r) || (i <= mid && a[i].a < a[j].a)){

			(tmp[k++] = a[i++]).is_sm = true;

		}else (tmp[k++] = a[j++]).is_sm = false;

	}

	copy(tmp+l,tmp+r+1,a+l);

	solve2(l,r);

}

int main(){

//	freopen("partial_order.in","r",stdin);

//	freopen("partial_order.out","w",stdout);

	read(n);

	for(int i=1;i<=n;++i) read(a[i].a);

	for(int i=1;i<=n;++i) read(a[i].b);

	for(int i=1;i<=n;++i) read(a[i].c);

	solve1(1,n);printf("%d\n",ans);

	getchar();getchar();

	return 0;

}

巴特西

四维偏序 CDQ套CDQ

对CDQ深一步的理解

四维偏序

题目大意

题解

Code

最新文章

热门文章