一、题目
二、解法
显然是 ( t kd) 树优化建图，和线段树优化建图差不多。
但是这道题要卡空间，所以我们用时间换空间，不建出边来，而是每次硬去 ( t kd) 树上面搜。
为什么思维难度这么小啊，但是我的代码打的很丑。
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int M = 200005;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,cnt,opt,rt,tot,f[M],ls[M],rs[M];
int L,R,D,U,mx[M][2],mi[M][2],dis[M];
int p1[M],p2[M],p3[M],p4[M],p5[M];
vector<int> p[M];
struct node
{
int x[2],id;
}a[M],v[M];
struct edge
{
int v,c,next;
}e[5*M];
struct zy
{
int u,c;
bool operator < (const zy &b) const
{
return c>b.c;
}
};priority_queue<zy> q;
bool cmp(node a,node b)
{
return a.x[opt]<b.x[opt];
}
void add(int u,int v,int c)
{
e[++tot]=edge{v,c,f[u]},f[u]=tot;
}
void up(int x)
{
for(int i=0;i<2;i++)
mx[x][i]=mi[x][i]=v[x].x[i];
for(int i=0;i<2;i++)
{
if(ls[x])
{
mx[x][i]=max(mx[x][i],mx[ls[x]][i]);
mi[x][i]=min(mi[x][i],mi[ls[x]][i]);
}
if(rs[x])
{
mx[x][i]=max(mx[x][i],mx[rs[x]][i]);
mi[x][i]=min(mi[x][i],mi[rs[x]][i]);
}
}
}
void build(int &x,int l,int r,int dep)
{
if(l>r) return ;
x=++cnt;
opt=dep%2;
int mid=(l+r)>>1;
nth_element(a+l,a+mid,a+r+1,cmp);
v[x]=a[mid];
add(x,a[mid].id,0);//这个虚点代表是实点
build(ls[x],l,mid-1,dep+1);
build(rs[x],mid+1,r,dep+1);
//下面连向儿子
if(ls[x]) add(x,ls[x],0);
if(rs[x]) add(x,rs[x],0);
up(x);
}
int out(int x)//判断x这个点是否全部不包含
{
return mi[x][0]>R || mx[x][0]<L || mi[x][1]>U || mx[x][1]<D;
}
int in(int a,int b,int c,int d)//是否全部包含
{
return L<=a && b<=R && D<=c && d<=U;
}
void ask(int x,int y,int t)
{
if(!x || out(x)) return ;//再见
if(in(mi[x][0],mx[x][0],mi[x][1],mx[x][1]))//全部包含,退出
{
if(dis[x]>dis[y]+t)
{
dis[x]=dis[y]+t;
q.push(zy{x,dis[x]});
}
return ;
}
if(in(v[x].x[0],v[x].x[0],v[x].x[1],v[x].x[1]))//如果单点包含
{
if(dis[v[x].id]>dis[y]+t)
{
dis[v[x].id]=dis[y]+t;
q.push(zy{v[x].id,dis[v[x].id]});
}
}
ask(ls[x],y,t);
ask(rs[x],y,t);
}
void dijk()
{
memset(dis,0x3f,sizeof dis);
q.push(zy{1,0});
dis[1]=0;
while(!q.empty())
{
zy t=q.top();q.pop();
if(t.c>dis[t.u]) continue;
for(int i=f[t.u];i;i=e[i].next)
{
int v=e[i].v,c=e[i].c;
if(dis[v]>dis[t.u]+c)
{
dis[v]=dis[t.u]+c;
q.push(zy{v,dis[v]});
}
}
if(t.u<=n)
{
for(int i=0;i<p[t.u].size();i++)
{
L=p2[p[t.u][i]];R=p3[p[t.u][i]];
D=p4[p[t.u][i]];U=p5[p[t.u][i]];
ask(rt,t.u,p1[p[t.u][i]]);
}
}
}
}
int main()
{
n=cnt=read();m=read();read();read();
for(int i=1;i<=n;i++)
a[i].x[0]=read(),a[i].x[1]=read(),a[i].id=i;
build(rt,1,n,0);
for(int i=1;i<=m;i++)
{
p[read()].push_back(i);
p1[i]=read();
p2[i]=read();
p3[i]=read();
p4[i]=read();
p5[i]=read();
}
dijk();
for(int i=2;i<=n;i++)
printf("%d
",dis[i]);
}