BZOJ4130：[PA2011]Kangaroos

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

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

这题跟\(BZOJ4358:permu\)一样。

不过我们需要把区间包含某个点改成判断区间是否有交点。

假设我们有俩区间\([l,r]\)与\([L,R]\)

假设俩不相交则满足：\(r<L||l>R\)；

假设有交：\(l<=R\)且\(L<=r\)

我们把询问区间当做点，把序列区间一个一个往\(K-D\)树里面搞。

那么就可以看做是把正交包围盒\([1,R][L,inf]\)。所以判断相交或者不相交就直接变成正交包围盒范围查询了。

判断不交的时候用大区间\([mn[0],mx[1]]\)，判断相交的时候用小区间\([mx[0],mn[1]]\)。由于卡常需求比较高，我就把\(struct\)改成\(namespace\)了。

时间复杂度：\(O(n\sqrt{n})\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

#include <algorithm>

using namespace std;

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

int ans[maxm];

int n,m,pps,X1,X2,Y1,Y2,L,R;

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 Kangaroos {int l,r;}a[maxn];

namespace T {

	int root;

	bool bo[maxm];

	int cnt[maxm],hismx[maxm];

	int add[maxm],cov[maxm],hiscov[maxm];

	struct point {

		int id,ls,rs;

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

		bool operator<(const point &a)const {

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

		}

	}p[maxm];

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

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

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

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

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

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

		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);

		}

		return u;

	}

	void prepare() {

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

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

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

			p[i].c[0]=read(),p[i].c[1]=read(),p[i].id=i;

		root=build(1,m,0);

	}

	void cov_tag(int u) {

		if(!bo[u])bo[u]=1,hiscov[u]=0;

		cnt[u]=cov[u]=0;

	}

	void add_tag(int u,int v) {

		if(!bo[u])add[u]+=v;

		else cov[u]+=v,hiscov[u]=max(hiscov[u],cov[u]);

		cnt[u]+=v,hismx[u]=max(hismx[u],cnt[u]);

	}

	void solve(int u,int v,int hisv) {

		bo[u]=1,hiscov[u]=max(hiscov[u],hisv);

		cnt[u]=cov[u]=v;

		hismx[u]=max(hismx[u],hiscov[u]);

	}

	void push_down(int u) {

		if(add[u]) {

			if(p[u].ls)add_tag(p[u].ls,add[u]);

			if(p[u].rs)add_tag(p[u].rs,add[u]);

			add[u]=0;

		}

		if(bo[u]) {

			if(p[u].ls)solve(p[u].ls,cov[u],hiscov[u]);

			if(p[u].rs)solve(p[u].rs,cov[u],hiscov[u]);

			bo[u]=0;

		}

	}

	void change(int u) {

		if(R<p[u].mn[0]||L>p[u].mx[1]) {cov_tag(u);return;}

		if(L<=p[u].mn[1]&&p[u].mx[0]<=R) {add_tag(u,1);return;}

		push_down(u);

		if(p[u].c[1]<L||p[u].c[0]>R)cnt[u]=0;

		else cnt[u]++,hismx[u]=max(hismx[u],cnt[u]);

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

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

	}

	void make_ans(int u) {

		ans[p[u].id]=hismx[u];

		push_down(u);

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

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

	}

}

int main() {

	n=read(),m=read();

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

		a[i].l=read(),a[i].r=read();

	T::prepare();

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

		L=a[i].l,R=a[i].r;

		T::change(T::root);

	}

	T::make_ans(T::root);

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

		printf("%d\n",ans[i]);

	return 0;

}

巴特西

BZOJ4130：[PA2011]Kangaroos

最新文章

热门文章