BZOJ2716：[Violet 3]天使玩偶

浅谈离线分治算法：https://www.cnblogs.com/AKMer/p/10415556.html

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

对于每个询问，分为四部分来做。

1、左下角：用\(x+y+tmp\)来更新答案，\(tmp\)表示在这个询问点的左下角的点中\(-x-y\)的最小值。

2、左上角：用\(x-y+tmp\)来更新答案，\(tmp\)表示在这个询问点的左上角的点中\(-x+y\)的最小值。

3、右上角：用\(-x-y+tmp\)来更新答案，\(tmp\)表示在这个询问点的右上角的点中\(x+y\)的最小值。

4、右下角：用\(-x+y+tmp\)来更新答案，\(tmp\)表示在这个询问点的右下角的点中\(x-y\)的最小值。

然后一开始就把序列排好序，像整体二分一样先统计当前层的信息再分流递归下去。略微卡常。

时间复杂度：\(O((n+m)log^2(n+m))\)

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

代码如下：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define low(i) ((i)&(-(i)))

const int maxn=5e5+5;

int ans[maxn];

int n,m,ans_cnt,maxlen;

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 Oper {

	int opt,id,x,y,tim;

	Oper() {}

	Oper(int _opt,int _id,int _x,int _y,int _tim) {

		opt=_opt,id=_id,x=_x,y=_y,tim=_tim;

	}

}p[maxn<<1],tmp[maxn<<1];

struct tree_array {

	int top;

	bool bo[1000005];

	int stk[1000005],c[1000005];

	void change(int pos,int v) {

		for(int i=pos;i<=maxlen;i+=low(i)) {

			if(!bo[i])bo[i]=1,stk[++top]=i;

			c[i]=min(c[i],v);

		}

	}

	void reset() {

		while(top)bo[stk[top]]=0,c[stk[top]]=c[0],top--;

	}

	int query(int pos) {

		int res=c[0];

		for(int i=pos;i;i-=low(i))

			res=min(res,c[i]);

		return res;

	}

}T[2];

bool cmp(Oper a,Oper b) {

	if(a.x==b.x)return a.tim<b.tim;

	return a.x<b.x;

}

void solve(int l,int r) {

	if(l==r)return;

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

	for(int i=l;i<=r;i++)

		if(p[i].opt==1&&p[i].tim<=mid) {

			T[0].change(p[i].y,-p[i].x-p[i].y);

			T[1].change(maxlen-p[i].y+1,-p[i].x+p[i].y);

		}

		else if(p[i].opt==2&&p[i].tim>mid) {

			ans[p[i].id]=min(ans[p[i].id],p[i].x+p[i].y+T[0].query(p[i].y));

			ans[p[i].id]=min(ans[p[i].id],p[i].x-p[i].y+T[1].query(maxlen-p[i].y+1));

		}

	T[0].reset(),T[1].reset();

	for(int i=r;i>=l;i--)

		if(p[i].opt==1&&p[i].tim<=mid) {

			T[0].change(p[i].y,p[i].x-p[i].y);

			T[1].change(maxlen-p[i].y+1,p[i].x+p[i].y);

		}

		else if(p[i].opt==2&&p[i].tim>mid) {

			ans[p[i].id]=min(ans[p[i].id],-p[i].x+p[i].y+T[0].query(p[i].y));

			ans[p[i].id]=min(ans[p[i].id],-p[i].x-p[i].y+T[1].query(maxlen-p[i].y+1));

		}

	T[0].reset(),T[1].reset();

	int cnt1=l,cnt2=mid+1;

	for(int i=l;i<=r;i++)

		if(p[i].tim<=mid)tmp[cnt1++]=p[i];

		else tmp[cnt2++]=p[i];

	for(int i=l;i<=r;i++)

		p[i]=tmp[i];

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

}

int main() {

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

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

		int x=read(),y=read();

		p[i]=Oper(1,0,x,y,i);

		maxlen=max(maxlen,y);

	}

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

		memset(T[i].c,127,sizeof(T[i].c));

	memset(ans,127,sizeof(ans));

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

		int opt=read(),x=read(),y=read(),id=opt==2?++ans_cnt:0;

		p[n+i]=Oper(opt,id,x,y,n+i),maxlen=max(maxlen,y);

	}

	sort(p+1,p+m+n+1,cmp);

	solve(1,n+m);

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

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

	return 0;

}

巴特西

BZOJ2716：[Violet 3]天使玩偶

最新文章

热门文章