title
analysis
\(32pts\) ：用结构体记录一下每个范围的连边， \(O(N^2)\) 暴力连边，然后跑一遍 \(Dijkstra\) 即可。
\(100pts\) ：考虑 \(Dijkstra\) 的过程：维护一个点集，每一次取出点集里到源点最近的点，用它去更新其他点到源点的距离，然后删除这个点。
那么我们就相当于要维护一个二维棋盘（格子上就是它到源点的距离），并支持以下的操作：
- 查询全局最小的点；
- 更新子矩阵里所有格子上的值；
- 删除某一个格子；
大概就是一个 \(K-D~tree\) 吧。
更新子矩阵就像线段树那样放标记，删除的时候像替罪羊树那样懒惰删除。
当然也有一种简单方法，详见 siruiyang_sry 。
下面回忆一下暑假的时候打同步赛的情况，真的是有些惨的，这道题说实在的，暴力分还是很好拿的（现在来看），我现在也不知道我在忙什么，反正是真的会了的东西，总是会的，就用上下的时间，好好把需要会的，熟练地掌握。
code
#include <bits/stdc++.h>
#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define Grt ch = getchar()
#define DeBug(x) std::cout << #x << " = " << x << std::endl
const int MaxN = 7e4 + 10, inf = 0x3f3f3f3f;
namespace IO
{
char buf[1<<15], *fs, *ft;
inline char getc() { return ft == fs && (ft = (fs = buf) + fread(buf, 1, 1<<15, stdin), ft == fs) ? 0 : *fs++; }
template <typename T> inline void read(T &x)
{
x = 0;
T f = 1, Grt;
while (!isdigit(ch) && ch ^ '-') Grt;
if (ch == '-') f = -1, Grt;
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), Grt;
x *= f;
}
template <typename T, typename... Args>
inline void read(T &x, Args &...args) { read(x); read(args...); }
char Out[1<<24], *fe = Out;
inline void flush() { fwrite(Out, 1, fe - Out, stdout); fe = Out; }
template <typename T> inline void write(T x, char str)
{
if (!x) *fe++ = 48;
if (x < 0) *fe++ = '-', x = -x;
T num = 0, ch[20];
while (x) ch[++ num] = x % 10 + 48, x /= 10;
while (num) *fe++ = ch[num --];
*fe++ = str;
}
}
using IO::read;
using IO::write;
template <typename T> inline bool chkMin(T &a, const T &b) { return a > b ? (a = b, true) : false; }
template <typename T> inline bool chkMax(T &a, const T &b) { return a < b ? (a = b, true) : false; }
template <typename T> inline T min(T a, T b) { return a < b ? a : b; }
template <typename T> inline T max(T a, T b) { return a > b ? a : b; }
struct point{int x, y;} o[MaxN];//存储每一个点
int cmptype, rank[MaxN];
inline bool cmp(int i, int j)
{
if (!cmptype) return o[i].x < o[j].x;
else return o[i].y < o[j].y;
}
namespace SGT
{
struct Orz{point p, lp, rp; int l, r, Max, Min, val, id, tag, vis;} c[MaxN];
int cnt = 0;
inline void pushup(int x)//维护节点所代表的的矩阵
{
if (c[x].vis) c[x].lp = (point){inf, inf}, c[x].rp = (point){-inf, -inf};
else c[x].lp = c[x].rp = c[x].p;
int l = c[x].l, r = c[x].r;
if (l)
{
chkMin(c[x].lp.x, c[l].lp.x);
chkMin(c[x].lp.y, c[l].lp.y);
chkMax(c[x].rp.x, c[l].rp.x);
chkMax(c[x].rp.y, c[l].rp.y);
}
if (r)
{
chkMin(c[x].lp.x, c[r].lp.x);
chkMin(c[x].lp.y, c[r].lp.y);
chkMax(c[x].rp.x, c[r].rp.x);
chkMax(c[x].rp.y, c[r].rp.y);
}
}
inline void update(int x)//维护子树的最大最小值（最大值可用于剪枝）
{
if (c[x].vis) c[x].Min = inf, c[x].Max = -inf;
else c[x].Min = c[x].Max = c[x].val;
int l = c[x].l, r = c[x].r;
if (l)
{
chkMax(c[x].Max, c[l].Max);
chkMin(c[x].Min, c[l].Min);
}
if (r)
{
chkMax(c[x].Max, c[r].Max);
chkMin(c[x].Min, c[r].Min);
}
}
inline int build(int l, int r, int type)
{
if (l > r) return 0;
cmptype = type;//记录此时的排序方式，因为是二维轮换建树
int mid = (l + r) >> 1, x = ++ cnt;
std::nth_element(rank + l, rank + mid, rank + r + 1, cmp);//令 rank[mid] 放在第 mid 位上，但不保证其他元素有序
c[x].p = o[rank[mid]], c[x].id = rank[mid], c[x].val = c[x].tag = inf, c[x].vis = 0;
if (c[x].id == 1) c[x].val = 0;//初始化这个节点
c[x].l = build(l, mid - 1, type ^ 1);//构造左右子树
c[x].r = build(mid + 1, r, type ^ 1);
pushup(x), update(x);
return x;
}
inline void addTag(int x, int v)//放标记：由于这个矩形内所有点到源点的距离会变得最大是 v ，所以最大值需要更新
{
if (v < c[x].Max && v < c[x].tag)
{
c[x].Max = c[x].tag = v, chkMin(c[x].Min, v);
if (!c[x].vis) chkMin(c[x].val, v);
}
}
inline void pushdown(int x)//下方标记，很类似于 Splay
{
if (c[x].tag == inf) return ;
if (c[x].l) addTag(c[x].l, c[x].tag);
if (c[x].r) addTag(c[x].r, c[x].tag);
c[x].tag = inf;
}
inline int find(int x, int v)//找到离源点距离为 v 的点
{
pushdown(x);
if (!c[x].vis && v == c[x].val)//除的时候注意要保留节点的 val ，因为统计答案的时候有用
{
c[x].vis = 1;
pushup(x), update(x);
return x;
}
int l = c[x].l, r = c[x].r;
if (l && v == c[l].Min)//向左子树寻找
{
int ans = find(l, v);
pushup(x), update(x);
return ans;
}
else//反之向右子树寻找
{
int ans = find(r, v);
pushup(x), update(x);
return ans;
}
}
inline void Change(int x, point tl, point tr, int v)//更新子矩阵
{
pushdown(x);
if (v >= c[x].Max) return ;//剪枝
if (tl.x > c[x].rp.x || tr.x < c[x].lp.x || tl.y > c[x].rp.y || tr.y < c[x].lp.y) return ;
if (tl.x <= c[x].lp.x && c[x].rp.x <= tr.x && tl.y <= c[x].lp.y && c[x].rp.y <= tr.y)
{
addTag(x, v);
return ;
}
if (!c[x].vis && tl.x <= c[x].p.x && c[x].p.x <= tr.x && tl.y <= c[x].p.y && c[x].p.y <= tr.y) chkMin(c[x].val, v);
if (c[x].l) Change(c[x].l, tl, tr, v);
if (c[x].r) Change(c[x].r, tl, tr, v);
update(x), pushup(x);
}
}
using SGT::build;
using SGT::find;
using SGT::Change;
using SGT::c;
struct edge{point lp, rp; int len;};
std::vector<edge> E[MaxN];
int ans[MaxN];
int main()
{
int n, m, W, H; read(n, m, W, H);
for (int i = 1; i <= n; ++ i) read(o[i].x, o[i].y), rank[i] = i;
for (int i = 1, p, t, l, r, u, d; i <= m; ++ i)
{
read(p, t, l, r, u, d);
E[p].push_back((edge){(point){l, u}, (point){r, d}, t});//记录边，要素：左上点，右下点，代价
}
int root = build(1, n, 0);//二维轮换建树
for (int i = 1; i <= n; ++ i)
{
int pos = find(root, c[root].Min);
int ip = c[pos].id;
ans[ip] = c[pos].val;//这里的 code 就很清晰了，不多解释
for (int j = 0; j < (int)E[ip].size(); ++ j) Change(root, E[ip][j].lp, E[ip][j].rp, ans[ip] + E[ip][j].len);
}//更新这个点所能到达的矩阵
for (int i = 2; i <= n; ++ i) write(ans[i], '\n');
IO::flush();
return 0;
}