P4514 上帝造题的七分钟 题解

Link

P4169 [Violet]天使玩偶/SJY摆棋子

Solve

我们先把式子简化一下，为了去掉绝对值符号，我们先统计(x,y)左下方的点，此时要求的式子被化简为

[min{(x-x_i)+(y-y_i)}=(x+y)-max{(x_i+y_i)} ]

此时题目就被转化为求最大的((x_i+y_i))满足(t_i<t,x_i<x,y_i<y)

就是典型的三位偏序，用树状数组维护((x+y))的最大值。

左上，右上，右下同理处理即可

Code

#include<bits/stdc++.h>
#define maxn 500005
#define point 1000003
#define inf 1047483647
using namespace std;
int n,m,ans[maxn],a[maxn],b[maxn],maxx[point+1];
struct memory{
	int t,x,y,ans;
}q[maxn];
struct angle{
	int x,y;
}p[maxn];
inline bool cmp(const angle x,const angle y){if(x.x!=y.x) return x.x<y.x;return x.y<y.y;}
inline void modify(int x,int v){for(register int i=x;i<=point;i+=i&-i) maxx[i]=max(maxx[i],v);}
inline int query(int x){int res=0;for(register int i=x;i;i-=i&-i) res=max(maxx[i],res);return res;}
inline void clear(int x){for(register int i=x;i<=point;i+=i&-i) maxx[i]=0;}
inline void cdq(int l,int r){
	if(l==r) return;int mid=l+r>>1;cdq(l,mid),cdq(mid+1,r);int i=l,j=mid+1,k=l;while(i<=mid&&j<=r){
		if(q[a[i]].x<=q[a[j]].x){if(q[a[i]].t==1) modify(q[a[i]].y,q[a[i]].x+q[a[i]].y);b[k++]=a[i++];}
		else{if(q[a[j]].t==2) q[a[j]].ans=max(q[a[j]].ans,query(q[a[j]].y));b[k++]=a[j++];}
	}
	while(j<=r){q[a[j]].ans=max(q[a[j]].ans,query(q[a[j]].y));b[k++]=a[j++];}
	for(register int ii=l;ii<i;ii++) if(q[a[ii]].t==1) clear(q[a[ii]].y);
	while(i<=mid) b[k++]=a[i++];for(register int ii=l;ii<=r;ii++) a[ii]=b[ii];
}
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-f;ch=getchar();}
	while(isdigit(ch)) ret=(ret<<1)+(ret<<3)+ch-'0',ch=getchar();
	return ret*f;
}
int main(){
	n=read(),m=read();for(register int i=1;i<=n;i++) p[i].x=read()+1,p[i].y=read()+1;sort(p+1,p+n+1,cmp);
	for(register int i=1;i<=m;i++) ans[i]=inf,q[i].t=read(),q[i].x=read()+1,q[i].y=read()+1;
	for(register int j=1;j<=4;j++){
		for(register int i=1;i<=m;i++) a[i]=i,q[i].ans=0;cdq(1,m);
		int l=1,r=1;while(l<=n&&r<=m){
			if(p[l].x<=q[a[r]].x) modify(p[l].y,p[l].x+p[l].y),l++;
			else{if(q[a[r]].t==2) q[a[r]].ans=max(q[a[r]].ans,query(q[a[r]].y));r++;}
		}
		while(r<=m){if(q[a[r]].t==2) if(q[a[r]].t==2) q[a[r]].ans=max(q[a[r]].ans,query(q[a[r]].y));r++;}memset(maxx,0,sizeof(maxx));
		for(register int i=1;i<=m;i++) if(q[i].t==2&&q[i].ans) ans[i]=min(ans[i],q[i].x+q[i].y-q[i].ans);
		if(j==4) break;if(j&1){
			for(register int i=1;i<=n;i++) p[i].y=point-p[i].y;
			for(register int i=1;i<=m;i++) q[i].y=point-q[i].y;
		}
		else{
			for(register int i=1;i<=n;i++) p[i].x=point-p[i].x;
			for(register int i=1;i<=n/2;i++) swap(p[i],p[n-i+1]);
			for(register int i=1;i<=m;i++) q[i].x=point-q[i].x;
		}
	}
	for(register int i=1;i<=m;i++) if(q[i].t==2) cout<<ans[i]<<'
';
	return 0;
}