一道比较困难的 CDQ 分治 题。
题目链接:Luogu P4169/BZOJ 2716/AcWing 254/Violet 3。
题目
题目描述
Ayu 在七年前曾经收到过一个天使玩偶,当时她把它当作时间囊埋在了地下。而七年后的今天,Ayu 却忘了她把天使玩偶埋在了哪里,所以她决定仅凭一点模糊的记忆来寻找它。
我们把 Ayu 生活的小镇看作一个二维平面坐标系,而 Ayu 会不定时地记起可能在某个点 $(x,y)$ 埋下了天使玩偶;或者 Ayu 会询问你,假如她在 $(x,y)$,那么她离近的天使玩偶可能埋下的地方有多远。
因为 Ayu 只会沿着平行坐标轴的方向来行动,所以在这个问题里我们定义两个点之间的距离为 $\operatorname{dist}(A,B)=|A_x-B_x|+|A_y-B_y|$。其中 $A_x$ 表示点 $A$ 的横坐标,其余类似。
数据范围
$$n,m\leq 3\times 10^5$$
$$0\leq x,y\leq 10^6$$
时空限制
题目 | 时间限制 | 空间限制 |
---|---|---|
Luogu P4169 | $$2-3\text{s}$$ | $$125\text{MiB}$$ |
BZOJ 2716 | $$?\text{s}$$ | $$?\text{MiB}$$ |
AcWing 254 | $$7\text{s}$$ | $$64\text{MiB}$$ |
Violet 3 | $$?\text{s}$$ | $$?\text{MiB}$$ |
题解
思路
发现是 CDQ 分治,然后就没有了。
代码
#include<bits/stdc++.h>
using namespace std;
#define reg register
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
reg bool f=false;
reg char ch=getchar();
reg int res=0;
while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
return f?-res:res;
}
const int MAXN=300000+5;
const int MAXM=300000+5;
const int MAXXY=1000000+5;
struct Node{
bool type;
int x,y,t;
inline Node(reg bool type=false,reg int x=0,reg int y=0,reg int t=0):type(type),x(x),y(y),t(t){
return;
}
inline bool operator<(const Node &a)const{
return x<a.x;
}
};
struct TreeArray{
#define lowbit(x) ( (x) & ( - (x) ) )
int n,unit[MAXXY];
inline void Init(reg int tot){
n=tot;
memset(unit,0,sizeof(unit));
return;
}
inline void Update(reg int ID,int val){
for(reg int i=ID;i<=n;i+=lowbit(i))
unit[i]=max(unit[i],val);
return;
}
inline int Query(reg int ID){
int res=0;
for(reg int i=ID;i;i-=lowbit(i))
res=max(res,unit[i]);
return res;
}
inline void Clear(reg int ID){
for(reg int i=ID;i<=n;i+=lowbit(i))
if(unit[i])
unit[i]=0;
else
break;
return;
}
#undef lowbit
};
int n,m;
int Maxx,Maxy;
int ans[MAXN+MAXM];
int tot,cnt;
TreeArray T;
Node Q[MAXN+MAXM],back[MAXN+MAXM];
inline void Init(void){
int rx=0,ry=0;
static Node temp[MAXN+MAXM];
cnt=0;
for(reg int i=1;i<=tot;++i)
if(!Q[i].type)
rx=max(rx,Q[i].x),ry=max(ry,Q[i].y);
for(reg int i=1;i<=tot;++i)
if(Q[i].x<=rx&&Q[i].y<=ry)
temp[++cnt]=Q[i];
for(reg int i=1;i<=cnt;++i)
Q[i]=temp[i];
return;
}
inline void Solve(reg int l,reg int r){
if(l==r)
return;
reg int mid=(l+r)>>1;
Solve(l,mid),Solve(mid+1,r);
reg int j=l;
for(reg int i=mid+1;i<=r;++i)
if(!Q[i].type){
while(j<=mid&&Q[j].x<=Q[i].x){
if(Q[j].type)
T.Update(Q[j].y,Q[j].x+Q[j].y);
++j;
}
reg int temp=T.Query(Q[i].y);
if(temp)
ans[Q[i].t]=min(ans[Q[i].t],Q[i].x+Q[i].y-temp);
}
for(reg int i=l;i<j;++i)
if(Q[i].type)
T.Clear(Q[i].y);
static Node temp[MAXN+MAXM];
merge(Q+l,Q+mid+1,Q+mid+1,Q+r+1,temp+l);
for(reg int i=l;i<=r;++i)
Q[i]=temp[i];
return;
}
int main(void){
n=read(),m=read();
for(reg int i=1;i<=n;++i){
static int x,y;
x=read()+1,y=read()+1;
++tot;
Q[tot]=Node(true,x,y,tot);
Maxx=max(Maxx,x),Maxy=max(Maxy,y);
}
while(m--){
static int k,x,y;
k=read(),x=read()+1,y=read()+1;
++tot;
Q[tot]=Node(k&1,x,y,tot);
Maxx=max(Maxx,x),Maxy=max(Maxy,y);
}
for(reg int i=1;i<=tot;++i)
back[i]=Q[i];
memset(ans,0X3F,sizeof(ans));
T.Init(Maxy);
Init();
Solve(1,cnt);
for(reg int i=1;i<=tot;++i){
Q[i]=back[i];
Q[i].x=Maxx-back[i].x+1;
}
Init();
Solve(1,cnt);
for(reg int i=1;i<=tot;++i){
Q[i]=back[i];
Q[i].y=Maxy-back[i].y+1;
}
Init();
Solve(1,cnt);
for(reg int i=1;i<=tot;++i){
Q[i]=back[i];
Q[i].x=Maxx-back[i].x+1;
Q[i].y=Maxy-back[i].y+1;
}
Init();
Solve(1,cnt);
for(reg int i=1;i<=tot;++i)
if(back[i].type==false)
printf("%d\n",ans[i]);
return 0;
}
近期评论