洛谷 P4169 [Violet]天使玩偶/SJY摆棋子 解题报告

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

上一篇:洛谷P4169 [Violet]天使玩偶/SJY摆棋子


下一篇:[Violet]天使玩偶/SJY摆棋子 [cdq分治]