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,m\le 300 000\)
\(x_i,y_i\le 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\n",ans[i]);
return 0;
}
2018.11.28