BZOJ4605：崂山白花蛇草水

浅谈\(K-D\) \(Tree\)：https://www.cnblogs.com/AKMer/p/10387266.html

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=4605

在写此题之余，我在某东上买了一箱\(24\)瓶装的崂山白花蛇草水，喝完就再续，准备一直喝到省选结束\(emm\)。

这题用权值线段树套\(kd\) \(tree\)即可轻松解决。不过需要用到类似于替罪羊树的重建。

另外可以加一个小优化，那就是只给线段树的右儿子建\(kd\) \(tree\)，因为对\(kd\) \(tree\)进行访问也只会发生在右儿子上。

时间复杂度：\(O(nlognlog10^9+nlog10^9\sqrt{n})\)

空间复杂度：\(O(nlogn+nlog10^9)\)

代码如下：

#include <cstdio>

#include <algorithm>

using namespace std;

#define bo11 (X2<p[u].mn[0]||p[u].mx[0]<X1)

#define bo12 (Y2<p[u].mn[1]||p[u].mx[1]<Y1)

#define bo21 (X1<=p[u].mn[0]&&p[u].mx[0]<=X2)

#define bo22 (Y1<=p[u].mn[1]&&p[u].mx[1]<=Y2)

#define bo31 (X1<=p[u].c[0]&&p[u].c[0]<=X2)

#define bo32 (Y1<=p[u].c[1]&&p[u].c[1]<=Y2)

const double alpha=0.75;

const int maxn=1e5+5,inf=2e9;

int n,m,ans,k,X1,Y1,X2,Y2,cnt,pps;

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

struct kd_tree {

	int tot,top;

	int id[maxn];

	struct point {

		int ls,rs,siz;

		int c[2],mn[2],mx[2];

		bool operator<(const point &a)const {

			return c[pps]<a.c[pps];

		}

	}p[maxn*20],tmp[maxn];

	void update(int u) {

		int ls=p[u].ls,rs=p[u].rs;

		p[u].siz=p[ls].siz+1+p[rs].siz;

		for(int i=0;i<2;i++) {

			int mn=min(p[ls].mn[i],p[rs].mn[i]);

			p[u].mn[i]=min(p[u].c[i],mn);

			int mx=max(p[ls].mx[i],p[rs].mx[i]);

			p[u].mx[i]=max(p[u].c[i],mx);

		}

	}

	void ins(int &u,int d) {

		if(!u) {

			u=++tot;

			p[u].c[0]=p[u].mn[0]=p[u].mx[0]=X1;

			p[u].c[1]=p[u].mn[1]=p[u].mx[1]=Y1;

			p[u].siz=1,p[u].ls=p[u].rs=0;return;

		}

		int num=d?Y1:X1;

		if(num<p[u].c[d])ins(p[u].ls,d^1);

		else ins(p[u].rs,d^1);

		update(u);

	}

	int rebuild(int l,int r,int d) {

		int mid=(l+r)>>1,u=id[mid];pps=d;

		nth_element(tmp+l,tmp+mid,tmp+r+1);

		p[u]=tmp[mid];

		if(l<mid)p[u].ls=rebuild(l,mid-1,d^1);

		if(r>mid)p[u].rs=rebuild(mid+1,r,d^1);

		update(u);return u;

	}

	void recycle(int u) {

		id[++top]=u;

		int ls=p[u].ls,rs=p[u].rs;

		p[u].mn[0]=p[u].mn[1]=inf;

		p[u].mx[0]=p[u].mx[1]=-inf;

		p[u].siz=1,p[u].ls=p[u].rs=0;

		tmp[top]=p[u];

		if(ls)recycle(ls);

		if(rs)recycle(rs);

	}

	void check(int &u,int d) {

		if(!u)return;

		int ls=p[u].ls,rs=p[u].rs;

		if(max(p[ls].siz,p[rs].siz)>alpha*p[u].siz) {

			top=0,recycle(u),u=rebuild(1,top,0);return;

		}

		int num=d?Y1:X1;

		if(num<p[u].c[d])check(p[u].ls,d^1);

		else check(p[u].rs,d^1);

	}

	void query(int u) {

		if(bo11||bo12)return;

		if(bo21&&bo22) {cnt+=p[u].siz;return;}

		if(bo31&&bo32) cnt++;

		if(p[u].ls)query(p[u].ls);

		if(p[u].rs)query(p[u].rs);

	}

}kd;

struct segment_tree {

	int tot;

	int ls[maxn*20],rs[maxn*20],rt[maxn*20];

	void ins() {

		int l=1,r=1e9,p=1,bo=1;

		while(1) {

			if(bo)kd.ins(rt[p],0),kd.check(rt[p],0);

			if(l==r)break;

			int mid=(l+r)>>1;

			if(k<=mid) {

				if(!ls[p])ls[p]=++tot;

				r=mid,p=ls[p],bo=0;

			}

			else {

				if(!rs[p])rs[p]=++tot;

				l=mid+1,p=rs[p],bo=1;

			}

		}

	}

	void query() {

		cnt=0;kd.query(rt[1]);

		if(cnt<k) {

			puts("NAIVE!ORZzyz.");

			ans=0;return;

		}

		int l=1,r=1e9,p=1;

		while(1) {

			if(l==r)break;

			int mid=(l+r)>>1;

			cnt=0;kd.query(rt[rs[p]]);

			if(cnt>=k)l=mid+1,p=rs[p];

			else r=mid,p=ls[p],k-=cnt;

		}

		ans=l;printf("%d\n",ans);

	}

}T;

int main() {

	n=read(),m=read();T.tot=1;

	kd.p[0].mn[0]=kd.p[0].mn[1]=inf;

	kd.p[0].mx[0]=kd.p[0].mx[1]=-inf;

	while(m--) {

		int opt=read();X1=read()^ans,Y1=read()^ans;

		if(opt==1)k=read()^ans,T.ins();

		else {

			X2=read()^ans,Y2=read()^ans,k=read()^ans;

			T.query();

		}

	}

	return 0;

}

巴特西

BZOJ4605：崂山白花蛇草水

最新文章

热门文章