P4169 [Violet]天使玩偶/SJY摆棋子
题目描述
(Ayu)在七年前曾经收到过一个天使玩偶，当时她把它当作时间囊埋在了地下。而七年后 的今天，(Ayu) 却忘了她把天使玩偶埋在了哪里，所以她决定仅凭一点模糊的记忆来寻找它。
我们把 (Ayu) 生活的小镇看作一个二维平面坐标系，而 (Ayu) 会不定时地记起可能在某个点 ((x,y)) 埋下了天使玩偶；或者 (Ayu) 会询问你，假如她在 ((x,y)) ，那么她离近的天使玩偶可能埋下的地方有多远。
因为 (Ayu) 只会沿着平行坐标轴的方向来行动，所以在这个问题里我们定义两个点之间的距离为(dist(A,B)=|A_x-B_x|+|A_y-B_y|)。其中 (A_x) 表示点 (A) 的横坐标，其余类似。
输入输出格式
输入格式：
第一行包含两个整数(n)和(m) ，在刚开始时，(Ayu) 已经知道有(n)个点可能埋着天使玩偶， 接下来 (Ayu) 要进行 (m) 次操作
接下来(n)行，每行两个非负整数 ((x_i,y_i))，表示初始 (n) 个点的坐标。
再接下来 (m) 行，每行三个非负整数 (t,x_i,y_i)。
如果 (t=1) ，则表示 (Ayu) 又回忆起了一个可能埋着玩偶的点 ((x_i,y_i)) 。
如果 (t=2) ，则表示 (Ayu) 询问如果她在点 ((x_i,y_i)) ，那么在已经回忆出来的点里，离她近的那个点有多远
输出格式：
对于每个(t=2)的询问，在单独的一行内输出该询问的结果。
说明
(n,mle 300 000)
(x_i,y_ile 1 000 000)
明明思路很简单..
最近状态不好啊..
考虑拆掉绝对值，然后我们会多出两个类似于偏序类型的条件，然后配合上时间，就是一个三维偏序问题了。
讨论四次可以转换一下坐标系。
注意位置是0的东西
懒得卡常吸氧气了
Code:
// luogu-judger-enable-o2
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
const int N=6e5+10;
const int M=1e6;
int n,m,k,s[M+10],ans[N];
inline int read()
{
int x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) {x=x*10+c-'0';c=getchar();}
return x;
}
struct node{int op,x,y;}q[N],qs[N],sq[N];
int min(int x,int y){return x<y?x:y;}
void add(int x,int d){while(x<=M)s[x]=s[x]>d?s[x]:d,x+=x&-x;}
void Clear(int x){while(x<=M)s[x]=0,x+=x&-x;}
int ask(int x){int mx=0;while(x)mx=mx>s[x]?mx:s[x],x-=x&-x;return mx==0?-M:mx;}
void CDQ(int l,int r)
{
if(l==r) return;
int mid=l+r>>1;
CDQ(l,mid),CDQ(mid+1,r);
register int lp=l,rp=mid+1,loc=l-1;
while(lp<=mid&&rp<=r)
{
if(q[lp].x<=q[rp].x)
{
if(!q[lp].op) add(q[lp].y,q[lp].x+q[lp].y);
sq[++loc]=q[lp++];
}
else
{
if(q[rp].op) ans[q[rp].op]=min(ans[q[rp].op],q[rp].x+q[rp].y-ask(q[rp].y));
sq[++loc]=q[rp++];
}
}
while(rp<=r)
{
if(q[rp].op) ans[q[rp].op]=min(ans[q[rp].op],q[rp].x+q[rp].y-ask(q[rp].y));
sq[++loc]=q[rp++];
}
for(register int i=l;i<lp;i++) if(!q[i].op) Clear(q[i].y);
while(lp<=mid) sq[++loc]=q[lp++];
for(register int i=l;i<=r;i++) q[i]=sq[i];
}
int main()
{
memset(ans,0x3f,sizeof(ans));
n=read(),m=read();
for(int i=1;i<=n;i++) qs[i].x=read()+1,qs[i].y=read()+1;
for(int i=1;i<=m;i++)
{
qs[i+n].op=read(),qs[i+n].x=read()+1,qs[i+n].y=read()+1;
if(--qs[i+n].op) qs[i+n].op=++k;
}
for(int i=1;i<=n+m;i++)
q[i]=qs[i];
CDQ(1,n+m);
for(int i=1;i<=n+m;i++)
q[i]={qs[i].op,M-qs[i].x,qs[i].y};
CDQ(1,n+m);
for(int i=1;i<=n+m;i++)
q[i]={qs[i].op,qs[i].x,M-qs[i].y};
CDQ(1,n+m);
for(int i=1;i<=n+m;i++)
q[i]={qs[i].op,M-qs[i].x,M-qs[i].y};
CDQ(1,n+m);
for(int i=1;i<=k;i++) printf("%d
",ans[i]);
return 0;
}
2018.11.28