description

Ayu 在七年前曾经收到过一个天使玩偶，当时她把它当作时间囊埋在了地下。而七年后的今天，Ayu 却忘了她把天使玩偶埋在了哪里，所以她决定仅凭一点模糊的记忆来寻找它。

我们把 Ayu 生活的小镇看作一个二维平面坐标系，而 Ayu 会不定时地记起可能在某个点 (xmy) 埋下了天使玩偶；或者 Ayu 会询问你，假如她在 (x,y) ，那么她离近的天使玩偶可能埋下的地方有多远。

因为 Ayu 只会沿着平行坐标轴的方向来行动，所以在这个问题里我们定义两个点之间的距离为dist(A,B)=|Ax-Bx|+|Ay-By|。其中 Ax 表示点 A的横坐标，其余类似。

data range

\[n,m\le 3\times 10^5
\]

solution

考虑控制\(t,x,y\)三维偏序之后，求出\(\le t\&\&\le x\&\&\le y\)的点中\(x+y\)的最大值

虽然之前用\(kd-tree\)做过

做完\(CDQ\)嵌套后感觉什么东西都可以暴力嵌套一波一样

于是一开始交了一个\(2\)重嵌套\(CDQ\)(三维偏序我也嵌套了...)，get \(61'\)

看来嵌套\(CDQ\)的常数还是十分巨大啊

改了\(BIT\)还需要卡常

旋转坐标又搞了好久

code

#include<bits/stdc++.h>

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<iomanip>

#include<cstring>

#include<complex>

#include<vector>

#include<cstdio>

#include<string>

#include<bitset>

#include<ctime>

#include<cmath>

#include<queue>

#include<stack>

#include<map>

#include<set>

#define Cpy(x,y) memcpy(x,y,sizeof(x))

#define Set(x,y) memset(x,y,sizeof(x))

#define FILE "a"

#define mp make_pair

#define pb push_back

#define RG register

#define il inline

using namespace std;

typedef unsigned long long ull;

typedef vector<int>VI;

typedef long long ll;

typedef double dd;

const dd eps=1e-6;

const int mod=1e9+7;

const int N=300010;

const int M=1000010;

const int inf=2147483647;

const ll INF=1e18+1;

const ll P=100000;

il ll read(){

	RG ll data=0,w=1;RG char ch=getchar();

	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();

	if(ch=='-')w=-1,ch=getchar();

	while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();

	return data*w;

}

il void file(){

	srand(time(NULL)+rand());

	freopen(FILE".in","r",stdin);

	freopen(FILE".out","w",stdout);

}

int n,m,rx[N],ry[N],k,q,a[M],w,ans[N];

int dx[]={1,0,1,0},dy[]={1,1,0,0};

il void ins(int i,int v){for(i++;i<=w;i+=(i&-i))a[i]=max(a[i],v);}

il int qry(int i){

	int r=a[0];for(i++;i;i-=(i&-i))r=max(r,a[i]);return r;}

il void clr(int i){for(i++;i<=w;i+=(i&-i))a[i]=a[0];}

struct point{int x,y;}r[N];

bool cmp2(point a,point b){if(a.x!=b.x)return a.x<b.x;return a.y<b.y;}

struct node{int t,x,y,d,id;}R[N],Q[N],tmp[N];

bool cmp1(node a,node b){

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

	if(a.y!=b.y)return a.y<b.y;

	return a.t<b.t;

}

void cdq(int l,int r){

	if(l==r)return;RG int mid=(l+r)>>1;cdq(l,mid);cdq(mid+1,r);

	for(RG int i=l,p1=l,p2=mid+1;i<=r;i++)

		if(p2>r||(p1<=mid&&cmp1(Q[p1],Q[p2]))){

			if(Q[p1].t==1)ins(Q[p1].y,Q[p1].d);tmp[i]=Q[p1++];

		}

		else{

			if(Q[p2].t==2)

				ans[Q[p2].id]=min(ans[Q[p2].id],Q[p2].d-qry(Q[p2].y));

			tmp[i]=Q[p2++];

		}

	for(RG int i=l;i<=r;i++){if(tmp[i].t==1)clr(tmp[i].y);Q[i]=tmp[i];}

}

int main()

{

	n=read();m=read();Set(ans,63);

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

		r[i].x=read();r[i].y=read();

		w=max(w,r[i].x+1);w=max(w,r[i].y+1);

	}

	sort(r+1,r+n+1,cmp2);

	for(RG int i=1,opt,x,y;i<=m;i++){

		opt=read();x=read();y=read();w=max(w,x+1);w=max(w,y+1);

		R[i]=(node){opt,x,y,0,(opt&1)?0:(++q)};

		if(opt==2)Q[q]=R[i];

	}

	sort(Q+1,Q+q+1,cmp1);

	for(RG int t=0,ix,iy,qx,qy,p;t<4;t++){

		Set(a,129);p=1;

		if(!dx[t])reverse(Q+1,Q+q+1),reverse(r+1,r+n+1);

		ix=dx[t]?r[p].x:(w-r[p].x);

		iy=dy[t]?r[p].y:(w-r[p].y);

		for(RG int i=1,p=1,ret;i<=q;i++){

			qx=dx[t]?Q[i].x:(w-Q[i].x);

			qy=dy[t]?Q[i].y:(w-Q[i].y);

			while(p<=n&&ix<=qx){

				ins(iy,ix+iy);p++;

				ix=dx[t]?r[p].x:(w-r[p].x);

				iy=dy[t]?r[p].y:(w-r[p].y);

			}

			ret=qx+qy-qry(qy);

			ans[Q[i].id]=min(ans[Q[i].id],ret);

		}

		if(!dx[t])reverse(Q+1,Q+q+1),reverse(r+1,r+n+1);

	}

	Set(a,129);

	for(RG int t=0;t<4;t++){

		Cpy(Q,R);

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

			Q[i].x=dx[t]?Q[i].x:(w-Q[i].x);

			Q[i].y=dy[t]?Q[i].y:(w-Q[i].y);

			Q[i].d=Q[i].x+Q[i].y;

		}

		cdq(1,m);

	}

	for(RG int i=1;i<=q;i++)printf("%d\n",ans[i]);

	return 0;

}

Ayu

[Violet]天使玩偶

description

data range

solution

code