BZOJ 2716 [Violet 3]天使玩偶 (CDQ分治、树状数组)

题目链接: https://www.lydsy.com/JudgeOnline/problem.php?id=2716

怎么KD树跑得都那么快啊。。我写的CDQ分治被暴虐

做四遍CDQ分治，每次求一个左下角\(x_i+y_i\)的最大值

第一种写法是一开始按时间排序，然后CDQ分治的时候改成按\(x\)坐标排序，同时用树状数组统计每个\(y\)坐标的最大值

第二种写法是一开始按\(x\)坐标排序，然后CDQ分支的时候改成按时间排序

CDQ分治好神奇(琦)。。。

一定要注意树状数组如果没有元素不能返回0! 我这么写然后test1 WA on line 40W+...

代码

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cassert>

#include<algorithm>

using namespace std;

const int N = 1e6;

const int C = 1e6+2;

struct Query

{

	int opt,x,y,id,ans;

	bool operator <(const Query &arg) const {return id<arg.id;}

} qr[N+3],qr2[N+3];

int tr[C+3];

int n,q,mx;

void modify(int lrb,int val)

{

	while(lrb<=mx)

	{

		tr[lrb] = max(tr[lrb],val);

		lrb += (lrb&(-lrb));

	}

}

int querymax(int rb)

{

	int ret = -C*2;

	while(rb>0)

	{

		ret = max(ret,tr[rb]);

		rb -= (rb&(-rb));

	}

	return ret;

}

void clear(int lrb)

{

	while(lrb<=mx && tr[lrb]!=-C*2)

	{

		tr[lrb] = -C*2;

		lrb += (lrb&(-lrb));

	}

}

void cdqdc(int lb,int rb)

{

	if(lb==rb) return;

	int mid = (lb+rb)>>1;

	int j = lb,k = mid+1;

	for(int i=lb; i<=rb; i++)

	{

		if(qr[i].id<=mid) {qr2[j] = qr[i]; j++;}

		else {qr2[k] = qr[i]; k++;}

	}

	for(int i=lb; i<=rb; i++) qr[i] = qr2[i];

	cdqdc(lb,mid);

	cdqdc(mid+1,rb);

	j = lb; k = mid+1;

	while(k<=rb)

	{

		while(j<=mid && qr[j].opt==2) j++;

		while(k<=rb && qr[k].opt==1) k++;

		if(k>rb) break;

		while(j<=mid && qr[j].x<=qr[k].x)

		{

			if(qr[j].opt==1) {modify(qr[j].y,qr[j].x+qr[j].y);}

			j++;

		}

		int tmp = querymax(qr[k].y);

		qr[k].ans = min(qr[k].ans,qr[k].x+qr[k].y-tmp);

		k++;

	}

	for(int i=lb; i<=mid; i++) {if(qr[i].opt==1) clear(qr[i].y);}

	j = lb; k = mid+1;

	for(int i=lb; i<=rb; i++)

	{

		if(j>mid || (k<=rb && qr[k].x<qr[j].x)) {qr2[i] = qr[k]; k++;}

		else {qr2[i] = qr[j]; j++;}

	}

	for(int i=lb; i<=rb; i++) qr[i] = qr2[i];

}

int main()

{

	scanf("%d%d",&n,&q);

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

	{

		scanf("%d%d",&qr[i].x,&qr[i].y); qr[i].opt = 1; qr[i].id = i; qr[i].x++; qr[i].y++; qr[i].ans = C*7;

		mx = max(mx,max(qr[i].x,qr[i].y));

	}

	for(int i=n+1; i<=n+q; i++)

	{

		scanf("%d%d%d",&qr[i].opt,&qr[i].x,&qr[i].y,&qr[i].opt); qr[i].id = i; qr[i].x++; qr[i].y++; qr[i].ans = C*7;

		mx = max(mx,max(qr[i].x,qr[i].y));

	}

	q+=n;

	for(int i=0; i<=mx; i++) tr[i] = -C*2;

	cdqdc(1,q);

	sort(qr+1,qr+q+1);

	for(int i=1; i<=q; i++) {qr[i].x = mx+1-qr[i].x;}

	cdqdc(1,q);

	sort(qr+1,qr+q+1);

	for(int i=1; i<=q; i++) {qr[i].y = mx+1-qr[i].y;}

	cdqdc(1,q);

	sort(qr+1,qr+q+1);

	for(int i=1; i<=q; i++) {qr[i].x = mx+1-qr[i].x;}

	cdqdc(1,q);

	sort(qr+1,qr+q+1);

	for(int i=1; i<=q; i++)

	{

		if(qr[i].opt==2) printf("%d\n",qr[i].ans);

	}

	return 0;

}