【[NOI2019]弹跳 [四分树+dijsktra]】传送门
打模拟赛只会线段树优化建图，于是只有72分
后来问 ldx 神仙学长，他说是个叫四分树的东西，我一脸懵逼？
他说线段树是一分为2，四方树是把一个矩阵一分为4
我想了想，好有道理啊！于是开始自己 yy
考虑动态开点，把每个点插入到树中，类似线段树，只会多log个节点
但优化建边的时候，每条边会想树上连log^2 个点，显然要凉
于是我想，dijsktra的时候在矩阵里面直接查然后更新最短路就可以了，不需要记录边
另外四方树更线段树一样啊，自己瞎写一下居然对了，真是个毒瘤的数据结构 !
#include
#define N 3000050
#define M 70050
using namespace std;
int read(){
int cnt = 0, f = 1;
char ch = 0;
while(!isdigit(ch)){ ch = getchar();
if(ch == '-') f = -1;
}
while(isdigit(ch)) cnt = (cnt << 1) + (cnt << 3) + (ch-'0'), ch = getchar();
return cnt * f;
}typedef long long ll;
int n, m, W, H;
struct Node{ int p, t, L, R, D, U;
};
vector v[M];
int rt, ch[N][4], res, pos[N], pre[N];
void Insert(int &u, int lx, int rx, int ly, int ry, int x, int y, int id){
if(!u) u = ++res;
if(lx == rx && ly == ry){ pos[id] = u;
pre[u] = id;
return;
}
int midx = (lx + rx) >> 1, midy = (ly + ry) >> 1;
if(x <= midx){
if(y <= midy) Insert(ch[u][0], lx, midx, ly, midy, x, y, id);
else Insert(ch[u][1], lx, midx, midy+1, ry, x, y, id);
}
else{
if(y <= midy) Insert(ch[u][2], midx+1, rx, ly, midy, x, y, id);
else Insert(ch[u][3], midx+1, rx, midy+1, ry, x, y, id);
}
}#define mp make_pair
ll dis[N];
bool vis[N];
priority_queue > q;
void Modify(int u, int lx, int rx, int ly, int ry, ll d, Node v){
if(!u) return;
if(dis[u] <= d + v.t) return;
if(v.L <= lx && rx <= v.R && v.D <= ly && ry <= v.U){
if(d + v.t < dis[u]){
dis[u] = d + v.t;
q.push(mp(-dis[u], u));
} return;
} int midx = (lx + rx) >> 1, midy = (ly + ry) >> 1;
if(ch[u][0] && v.L <= midx && v.D <= midy) Modify(ch[u][0], lx, midx, ly, midy, d, v);
if(ch[u][1] && v.L <= midx && v.U > midy) Modify(ch[u][1], lx, midx, midy+1, ry, d, v);
if(ch[u][2] && v.R > midx && v.D <= midy) Modify(ch[u][2], midx+1, rx, ly, midy, d, v);
if(ch[u][3] && v.R > midx && v.U > midy) Modify(ch[u][3], midx+1, rx, midy+1, ry, d, v);
}int main(){
freopen("jump.in","r",stdin);
freopen("jump.out","w",stdout);
n = read(), m = read(), W = read(), H = read();
res = n;
for(int i=1;
i<=n;
i++){
int x = read(), y = read();
Insert(rt, 1, W, 1, H, x, y, i);
}
for(int i=1;
i<=m;
i++){
int p = read(), t = read(), L = read(), R = read(), D = read(), U = read();
v[p].push_back((Node){p, t, L, R, D, U});
} memset(dis, 127, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[pos[1]] = 0;
q.push(mp(0, pos[1]));
while(!q.empty()){
int x = q.top().second;
q.pop();
if(vis[x]) continue;
vis[x] = true;
if(pre[x]){
for(int i=0;
i dis[x]){
dis[ch[x][j]] = dis[x];
q.push(mp(-dis[ch[x][j]], ch[x][j]));
}
}
}
}
for(int i=2;
i<=n;
i++) printf("%lld\n", dis[pos[i]]);
return 0;
} 
