Description
给出 (n) 个商店,每个商店用一个四元组 ((x,t,a,b)) 表示 ,表示坐标为 (x) ,种类为 (t) ,出现时间为 ([a,b])
每次询问一个点 ((l_i,y_i)) ,表示一个人在 (y_i) 时刻在位置 (l_i) ,求它到达每一种商店的最小距离的最大值
Solution
扫描线维护每一个商店
首先要想到二分一个答案 (mid)
那么就只需要判断是否每一个种类的商店都出现在区间 ([l_i-mid,l_i+mid])
对于商店维护一个 (pre_i) 表示 (i) 之前第一个与它同类的商店的位置
依次考虑每一类商店的话,那么只需要判断 (l_i+mid) 之后的第一个该类的商店 (pre_i) 是否在区间内就行了
对于所有的种类我们放在同一棵平衡树里面,然后把所有位置大于 (l_i+mid) 的 (pre_i) 的取 (min) 就行了
复杂度 (O(n*log^2)) , 仿佛在线段树上做这些操作可以做到 (O(n*log)) ?
#include<bits/stdc++.h>
using namespace std;
template<class T>void gi(T &x){
int f;char c;
for(f=1,c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
for(x=0;c<='9'&&c>='0';c=getchar())x=x*10+(c&15);x*=f;
}
const int N=1e6+10,inf=4e8+10;
int n,K,Q,cnt=0,ans[N],ch[N][2],fa[N],rt=0,tot=0,a[N],pre[N],w[N];
struct st{int x,id;};
inline bool operator <(const st &p,const st &q){return p.x<q.x;}
multiset<st>V[N/4];multiset<st>::iterator it;
inline void upd(int x){
int ls=ch[x][0],rs=ch[x][1];w[x]=pre[x];
if(ls && a[w[ls]]<a[w[x]])w[x]=w[ls];
if(rs && a[w[rs]]<a[w[x]])w[x]=w[rs];
}
inline void rotate(int x){
int y=fa[x];bool t=ch[y][1]==x;
ch[y][t]=ch[x][!t];fa[ch[y][t]]=y;
ch[x][!t]=y;fa[x]=fa[y];
if(fa[y])ch[fa[y]][ch[fa[y]][1]==y]=x;
fa[y]=x;upd(y);upd(x);
}
inline void splay(int x,int goal){
while(fa[x]!=goal){
int y=fa[x],p=fa[y];
if(p==goal)rotate(x);
else if((ch[p][0]==y)==(ch[y][0]==x))rotate(y),rotate(x);
else rotate(x),rotate(x);
}if(!goal)rt=x;
}
inline void ins(int &x,int k,int la){
if(!x){x=++tot;fa[x]=la;a[x]=k;splay(x,0);return ;}
ins(ch[x][k>a[x]],k,x);
}
inline void del(int x){
splay(x,0);
int p=ch[x][0],q=ch[x][1];
while(ch[p][1])p=ch[p][1];
while(ch[q][0])q=ch[q][0];
splay(p,0);splay(q,p);ch[q][0]=fa[x]=0;upd(q);
}
struct data{int op,x,p,k;}q[N];
inline bool operator <(data p,data q){return p.x!=q.x?p.x<q.x:p.op<q.op;}
inline void add(int x,int k){
ins(rt,x,0);
it=V[k].upper_bound((st){x,0});
w[tot]=pre[tot]=pre[it->id];
splay(it->id,0);
w[it->id]=pre[it->id]=tot;
V[k].insert((st){x,tot});
}
inline void Del(int x,int k){
it=V[k].lower_bound((st){x,0});
int s=it->id,t=(++it)->id;
splay(t,0);
w[t]=pre[t]=pre[s];
splay(s,0);
w[s]=pre[s]=0;
V[k].erase(--it);del(s);
}
inline int getpre(int k){
int x=rt,ret=0;
while(x){
if(a[x]<=k)ret=x,x=ch[x][1];
else x=ch[x][0];
}return ret;
}
inline int query(int x){
x=getpre(x);splay(x,0);
return a[w[ch[x][1]]];
}
inline int qry(int x){
int l=0,r=1e8,mid,ret=-1;
while(l<=r){
mid=(l+r)>>1;
if(query(x+mid)>=x-mid)ret=mid,r=mid-1;
else l=mid+1;
}
return ret;
}
int main(){
freopen("pp.in","r",stdin);
freopen("pp.out","w",stdout);
int x,y,l,r;
cin>>n>>K>>Q;
for(int i=1;i<=K;i++){
ins(rt,inf,0);V[i].insert((st){inf,tot});pre[tot]=tot+1;
ins(rt,-inf,0);V[i].insert((st){-inf,tot});
}
for(int i=1;i<=n;i++){
gi(x);gi(y);gi(l);gi(r);
q[++cnt]=(data){-1,l,x,y};q[++cnt]=(data){1,r,x,y};
}
for(int i=1;i<=Q;i++)gi(x),gi(y),q[++cnt]=(data){0,y,x,i};
sort(q+1,q+cnt+1);
for(int i=1;i<=cnt;i++){
if(q[i].op==-1)add(q[i].p,q[i].k);
else if(q[i].op==1)Del(q[i].p,q[i].k);
else ans[q[i].k]=qry(q[i].p);
}
for(int i=1;i<=Q;i++)printf("%d
",ans[i]);
return 0;
}