CDQ分治2

CDQ套CDQ：四维偏序问题

题目来源：COGS 2479 偏序

#define LEFT 0

#define RIGHT 1

struct Node{int a,b,c,d,bg;};

Node q[_],tmp1[_],tmp2[_];  int aa,bb,cc,dd,n; long long Ans;

void cdq2(RG int L,RG int R){

	if(L == R)return;

	RG int mid = (L+R)>>1; cdq2(L,mid); cdq2(mid+1,R);

	RG int oo = L , l = L , r = mid + 1;

	while(l <= mid && r <= R){

		if(tmp1[l].c < tmp1[r].c){

		    if(tmp1[l].bg == LEFT)BIT:: Update(tmp1[l].d);

		    tmp2[oo++] = tmp1[l++];

		}

		else {

			if(tmp1[r].bg == RIGHT)Ans += BIT::Query(tmp1[r].d);

			tmp2[oo++] = tmp1[r++];

		}

	}

	while(l <= mid)tmp2[oo++] = tmp1[l++];

	while(r <= R){

	    if(tmp1[r].bg == RIGHT)Ans += BIT::Query(tmp1[r].d) ;

		tmp2[oo++] = tmp1[r++];

	}

	for(RG int i = L; i <= R; i ++){

	    if(tmp2[i].bg == LEFT)BIT::Clear(tmp2[i].d);

	    tmp1[i] = tmp2[i];

	}

	return;

}

void cdq1(int L,int R){

	if(L == R)return;

	RG int mid = (L+R)>>1; cdq1(L,mid);  cdq1(mid+1,R);

	RG int oo = L , l = L ,r = mid + 1;

	while(l <= mid && r <= R){

		if(q[l].b < q[r].b)

		   q[l].bg = LEFT ,

		   tmp1[oo++] = q[l++] ;

		else

		   q[r].bg = RIGHT ,

		   tmp1[oo++] = q[r++] ;

	}

	while(l <= mid)q[l].bg = LEFT , tmp1[oo++] = q[l++];

	while(r <= R)q[r].bg = RIGHT , tmp1[oo++] = q[r++];

	for(RG int i = L; i <= R; i ++)q[i] = tmp1[i];

	cdq2(L,R);

}

int main(){

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

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

	n = gi();

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

	for(RG int i = 1; i <= n; i ++)q[i].b = gi();

	for(RG int i = 1; i <= n; i ++)q[i].c = gi();

	for(RG int i = 1; i <= n; i ++)q[i].d = gi();

	Ans = 0; cdq1(1,n);

	cout<<Ans;  return 0;

}

CDQ套CDQ套CDQ：五维偏序问题

题目来源：COGS 2580 偏序 \(II\)

#define LEFT 0

#define RIGHT 1

struct Node{int d1,d2,d3,d4,d5,bg[2];};

Node q[_] , tmp1[_] , tmp2[_] , tmp3[_];  int n; long long ans;

IL bool Check(RG int id,RG int opt)

{return tmp2[id].bg[0]==opt && tmp2[id].bg[1]==opt;}

void cdq3(RG int L,RG int R){      //cdq分治解决三维偏序问题

	if(L == R)return;

	RG int mid = (L+R)>>1; cdq3(L,mid); cdq3(mid+1,R);

	RG int l = L , r = mid+1 , oo = L-1;

	while(l <= mid && r <= R){

		if(tmp2[l].d4 < tmp2[r].d4){

			if(Check(l,LEFT))BIT::Update(tmp2[l].d5);

			tmp3[++oo] = tmp2[l++];

		}

		else{

			if(Check(r,RIGHT))ans += BIT::Query(tmp2[r].d5);

			tmp3[++oo] = tmp2[r++];

		}

	}

	while(l <= mid)tmp3[++oo] = tmp2[l++];

	while(r <= R){

	    if(Check(r,RIGHT))ans += BIT::Query(tmp2[r].d5);

	    tmp3[++oo] = tmp2[r++];

	}

	for(RG int i = L; i <= R; i ++){

	   if(Check(i,LEFT))BIT::Clear(tmp2[i].d5);

	   tmp2[i] = tmp3[i];

    }

	return;

}

void cdq2(RG int L,RG int R){       //消去第三维的影响

	if(L == R)return;

	RG int mid = (L+R)>>1; cdq2(L,mid); cdq2(mid+1,R);

	RG int l = L , r = mid+1 , oo = L-1;

	while(l <= mid && r <= R){

		if(tmp1[l].d3 < tmp1[r].d3)

			tmp1[l].bg[1] = LEFT , tmp2[++oo] = tmp1[l++];

		else

			tmp1[r].bg[1] = RIGHT , tmp2[++oo] = tmp1[r++];

	}

	while(l <= mid)tmp1[l].bg[1] = LEFT , tmp2[++oo] = tmp1[l++];

	while(r <= R)tmp1[r].bg[1] = RIGHT , tmp2[++oo] = tmp1[r++];

	for(RG int i = L; i <= R; i ++)tmp1[i] = tmp2[i];

	cdq3(L,R); 

}

void cdq1(RG int L,RG int R){         //消去第二维的影响

	if(L == R)return;

	RG int mid = (L+R)>>1; cdq1(L,mid); cdq1(mid+1,R);

	RG int l = L , r = mid+1 , oo = L-1;

	while(l <= mid && r <= R){

		if(q[l].d2 < q[r].d2)

		    q[l].bg[0] = LEFT , tmp1[++oo] = q[l++];

		else

		    q[r].bg[0] = RIGHT , tmp1[++oo] = q[r++];

	}

	while(l<=mid)q[l].bg[0] = LEFT , tmp1[++oo] = q[l++];

	while(r<=R)q[r].bg[0] = RIGHT , tmp1[++oo] = q[r++];

	for(RG int i = L; i <= R; i ++)q[i] = tmp1[i];

	cdq2(L,R);

}

int main(){

	freopen("partial_order_two.in","r",stdin);

	freopen("partial_order_two.out","w",stdout);

	n = gi();

	for(RG int i = 1; i <= n; i ++)q[i].d1 = i;

	for(RG int i = 1; i <= n; i ++)q[i].d2 = gi();

	for(RG int i = 1; i <= n; i ++)q[i].d3 = gi();

	for(RG int i = 1; i <= n; i ++)q[i].d4 = gi();

	for(RG int i = 1; i <= n; i ++)q[i].d5 = gi();

	//sort_a  消去第一维的影响

	ans = 0; cdq1(1,n);

	cout << ans;  return 0;

}