Legend
有 (n (1 le n le 70000)) 个二维平面上的点，(m (1 le m le 150000)) 条集体边，每条集体边为从某个点向一个矩形所在的所有点连边。
求 (1) 到所有点的最短路。
时空限制：( extrm{2s/128MB})。
Editorial
很容易让人想到 ( m{xxx}) 优化建图，发现非常无趣的是，二维线段树是两个 (log)。被卡啦！
于是我们果断用 ( m{kdtree})！发现还是被卡空间啦！
于是我们考虑不把边建出来，而是直接对整棵子树取 (min)。
( m{kdtree}) 恰好是一棵平衡树，也可以维护全局最小值！
所以你就可以很方便的写 ( m{Dijkstra}) 啦！
复杂度？(O(m sqrt{n}))！
Code
-
( m{kdtree}) 真的难写。
-
( m{kdtree}) 不剪枝？( m{TLE}) 欢迎你。
#include <bits/stdc++.h>
#define debug(...) ;
// fprintf(stderr ,__VA_ARGS__)
#define __FILE(x)
freopen(#x".in" ,"r" ,stdin);
freopen(#x".out" ,"w" ,stdout)
int read(){
char k = getchar(); int x = 0;
while(k < '0' || k > '9') k = getchar();
while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar();
return x;
}
inline void chkmin(int &x ,int y){x = std::min(x ,y);}
inline void chkmax(int &x ,int y){x = std::max(x ,y);}
const int MX = 2e5 + 233;
struct point{
int x[2] ,w ,id;
point(int X ,int Y ,int W = 0 ,int ID = 0){x[0] = X ,x[1] = Y ,w = W ,id = ID;}
point(int a[2] ,int W = 0 ,int ID = 0){x[0] = a[0] ,x[1] = a[1] ,w = W ,id = ID;}
point(){x[0] = x[1] = id = 0 ,w = INT_MAX;}
}P[MX];
struct node{
int mn[2] ,mx[2] ,ch[2];
int del ,covmn ,mnval ,mnfr ,val ,alive;
int mxval;
point tp;
};
int D;
bool operator <(point a ,point b){return a.x[D] < b.x[D];}
int trans[MX] ,tkdt[MX];
struct KDT{
#define lch tr[x].ch[0]
#define rch tr[x].ch[1]
node tr[MX] ;
int cnt ,rt ,D;
KDT(){
for(int i : {0 ,1}){
tr[0].mx[i] = INT_MIN;
tr[0].mn[i] = INT_MAX;
}
tr[0].covmn = tr[0].mnval = tr[0].val = INT_MAX;
tr[0].mnfr = tr[0].alive = false;
tr[0].del = true;
tr[0].mxval = INT_MIN;
}
void docovmn(int x ,int v){
if(!tr[x].del) chkmin(tr[x].val ,v);
if(tr[x].alive){
chkmin(tr[x].mnval ,v);
chkmin(tr[x].covmn ,v);
chkmin(tr[x].mxval ,v);
}
}
void _pushup(int x){
if(!tr[x].del){
tr[x].mnval = tr[x].val;
tr[x].mxval = tr[x].val;
tr[x].mnfr = x;
}
else{
tr[x].mnfr = 0 ,tr[x].mnval = INT_MAX;
tr[x].mxval = INT_MIN;
}
tr[x].alive = tr[lch].alive || tr[rch].alive || !tr[x].del;
for(int i : {0 ,1}){
tr[x].mn[i] = tr[x].mx[i] = tr[x].tp.x[i];
for(int j : {lch ,rch}){
chkmin(tr[x].mn[i] ,tr[j].mn[i]);
chkmax(tr[x].mx[i] ,tr[j].mx[i]);
chkmin(tr[x].mnval ,tr[j].mnval);
chkmax(tr[x].mxval ,tr[j].mxval);
if(tr[x].mnval == tr[j].mnval){
tr[x].mnfr = tr[j].mnfr;
}
}
}
}
void pushup(int x){
if(!tr[x].del){
tr[x].mnval = tr[x].val;
tr[x].mxval = tr[x].val;
tr[x].mnfr = x;
}
else{
tr[x].mnfr = 0 ,tr[x].mnval = INT_MAX;
tr[x].mxval = INT_MIN;
}
tr[x].alive = tr[lch].alive || tr[rch].alive || !tr[x].del;
for(int j : {lch ,rch}){
chkmin(tr[x].mnval ,tr[j].mnval);
chkmax(tr[x].mxval ,tr[j].mxval);
if(tr[x].mnval == tr[j].mnval){
tr[x].mnfr = tr[j].mnfr;
}
}
}
void pushdown(int x){
if(tr[x].covmn != INT_MAX){
if(lch) docovmn(lch ,tr[x].covmn);
if(rch) docovmn(rch ,tr[x].covmn);
tr[x].covmn = INT_MAX;
}
}
void outputinfo(int x){
debug("Info of vertex %d:
" ,x);
debug("> val = %d ,mnval = %d ,mnvalfrom = %d
" ,tr[x].val ,tr[x].mnval ,tr[x].mnfr);
debug("> point = (%d ,%d)
" ,tr[x].tp.x[0] ,tr[x].tp.x[1]);
}
int build(int L ,int R ,int d = 1){
if(L > R) return 0;
int mid = (L + R) >> 1 ,x = mid;
D = d ,std::nth_element(P + L ,P + mid ,P + R + 1);
trans[mid] = P[mid].id;
tkdt[P[mid].id] = mid;
tr[x].tp = P[mid];
tr[x].covmn = INT_MAX;
tr[x].val = tr[x].tp.w;
lch = build(L ,mid - 1 ,!d);
rch = build(mid + 1 ,R ,!d);
_pushup(x);
// outputinfo(x);
return x;
}
void buildtree(int L ,int R){rt = build(L ,R);}
bool inside(point A ,point B ,point C ,point D){
// check if AB is in CD
for(int i : {0 ,1}){
if(!(C.x[i] <= A.x[i] && B.x[i] <= D.x[i])){
return false;
}
}
return true;
}
bool outside(point A ,point B ,point C ,point D){
return B.x[0] < C.x[0] || A.x[0] > D.x[0]
|| B.x[1] < C.x[1] || A.x[1] > D.x[1];
}
void upd(point A ,point B ,int x ,int v){
if(!x) return;
pushdown(x);
if(inside(tr[x].mn ,tr[x].mx ,A ,B)){return docovmn(x ,v);}
if(tr[x].mxval <= v || outside(tr[x].mn ,tr[x].mx ,A ,B) || !tr[x].alive){return;}
if(inside(tr[x].tp ,tr[x].tp ,A ,B) && !tr[x].del){
debug("upd (%d ,%d) by %d
" ,tr[x].tp.x[0] ,tr[x].tp.x[1] ,v);
tr[x].val = std::min(tr[x].val ,v);
}
upd(A ,B ,lch ,v) ,upd(A ,B ,rch ,v);
return pushup(x);
}
void del(point A ,int x){
if(!x) return ;
if(outside(A ,A ,tr[x].mn ,tr[x].mx) || !tr[x].alive) return;
pushdown(x);
if(inside(tr[x].tp ,tr[x].tp ,A ,A)){
tr[x].del = true;
pushup(x);
return ;
}
del(A ,lch) ,del(A ,rch);
pushup(x);
}
std::pair<int ,int> getmn(){
return std::make_pair(tr[rt].mnval ,tr[rt].mnfr);
}
void pushall(int x){
if(!x) return;
pushdown(x);
pushall(lch) ,pushall(rch);
pushup(x);
outputinfo(x);
}
}kdt;
struct Edge{
int w;
point A ,B;
Edge(){w = 0 ,A = B = point();}
Edge(int dist ,point a ,point b){
w = dist;
A = a ,B = b;
}
};
std::vector<Edge> e[MX];
int dis[MX];
int main(){
__FILE([NOI2019]弹跳);
int n = read() ,m = read() ,w = read() ,h = read();
for(int i = 1 ,x ,y ; i <= n ; ++i){
x = read() ,y = read();
P[i] = point(x ,y ,(INT_MAX) >> 1 ,i);
}
kdt.buildtree(1 ,n);
for(int i = 1 ,p ,t ,L1 ,R1 ,L2 ,R2 ; i <= m ; ++i){
p = read() ,t = read();
L1 = read() ,L2 = read() ,R1 = read() ,R2 = read();
e[p].push_back(Edge(t ,point(L1 ,R1) ,point(L2 ,R2)));
}
memset(dis ,0x3f ,sizeof dis);
kdt.upd(P[tkdt[1]] ,P[tkdt[1]] ,kdt.rt ,0);
for(int i = 1 ; i <= n ; ++i){
// kdt.pushall(kdt.rt);
std::pair<int ,int> cur = kdt.getmn();
int x = trans[cur.second] ,dist = cur.first;
debug("%d updated
" ,x);
kdt.del(P[cur.second] ,kdt.rt);
dis[x] = dist;
for(auto j : e[x]){
debug("$ TRY to update from %d...
" ,x);
kdt.upd(j.A ,j.B ,kdt.rt ,dist + j.w);
}
}
for(int i = 2 ; i <= n ; ++i){
printf("%d
" ,dis[i]);
}
return 0;
}