洛谷 P5471 [NOI2019]弹跳 KDtree

我们观察题目后发现这很明显是一道有关最短路的题，首先可以无脑打一个最短路模板上去。

36分

#include
#include
#include
#include
#define pr pair
using namespace std;
int n, m, w, h, tot;
const int N = 70010, M = 150000;
int head[N], dis[N], vis[N], to[M], nt[M], val[M];
priority_queueq;
struct dian {int x, y;} d[N];
struct tiao {int p, t, l, r, d, u;} t[M];
inline int read()
{
	int res = 0; char ch = getchar(); bool XX = false;
	for (; !isdigit(ch); ch = getchar())(ch == '-') && (XX = true);
	for (; isdigit(ch); ch = getchar())res = (res << 3) + (res << 1) + (ch ^ 48);
	return XX ? -res : res;
}
void add(int f, int t, int d)
{
	to[++tot] = t; val[tot] = d; nt[tot] = head[f]; head[f] = tot;
}
void DIJ()
{
	int x;
	memset(dis, 0x3f, sizeof(dis));
	q.push(pr(0, 1)); dis[1] = 0;
	while (!q.empty())
	{
		x = q.top().second; q.pop();
		if (vis[x])continue; vis[x] = 1;
		for (int i = head[x]; i; i = nt[i])
			if (dis[to[i]] > dis[x] + val[i])
			{
				dis[to[i]] = dis[x] + val[i];
				q.push(pr(-dis[to[i]], to[i]));
			}
	}
}
int main()
{
	cin >> n >> m >> w >> h;
	for (int i = 1; i <= n; ++i)d[i].x = read(), d[i].y = read();
	for (int i = 1; i <= m; ++i)
	{
		t[i].p = read(), t[i].t = read(), t[i].l = read(), t[i].r = read(), t[i].d = read(), t[i].u = read();
		for (int j = 1; j <= n; ++j)
			if (j != t[i].p && t[i].l <= d[j].x && d[j].x <= t[i].r && t[i].d <= d[j].y && d[j].y <= t[i].u)add(t[i].p, j, t[i].t);
	}
	DIJ();
	for (int i = 2; i <= n; ++i)printf("%d\n", dis[i]);
	return 0;
}

思考对于 \(h=1\) 的数据，我们可以用线段树优化建图水过。

那 \(h！=1\) 的话，我们用二维数据结构优化建图就行，这里我用的是 \(KDtree\)

#include
#include
#include
#include
#include
#define lson ch[k][0]
#define rson ch[k][1]
#define pr pair
using namespace std;
int n, m, w, h, tot, num, root, nowk;
const int N = 140010, M = 3000010;
int head[N], dis[N], vis[N], to[M], nt[M], val[M], s[N], ch[N][2], minx[N], miny[N], maxx[N], maxy[N];
priority_queueq;
struct dian {int x, y, id;} d[N];
struct tiao {int p, t, l, r, d, u;} t[M];
inline int read()
{
	int res = 0; char ch = getchar(); bool XX = false;
	for (; !isdigit(ch); ch = getchar())(ch == '-') && (XX = true);
	for (; isdigit(ch); ch = getchar())res = (res << 3) + (res << 1) + (ch ^ 48);
	return XX ? -res : res;
}
void add(int f, int t, int d)
{
	to[++tot] = t; val[tot] = d; nt[tot] = head[f]; head[f] = tot;
}
void pushup(int k)
{
	minx[k] = maxx[k] = d[k - n].x; miny[k] = maxy[k] = d[k - n].y; add(k, k - n, 0);
	if (lson)minx[k] = min(minx[k], minx[lson]), maxx[k] = max(maxx[k], maxx[lson]), miny[k] = min(miny[k], miny[lson]), maxy[k] = max(maxy[k], maxy[lson]), add(k, lson, 0);
	if (rson)minx[k] = min(minx[k], minx[rson]), maxx[k] = max(maxx[k], maxx[rson]), miny[k] = min(miny[k], miny[rson]), maxy[k] = max(maxy[k], maxy[rson]), add(k, rson, 0);
}
int my(int a, int b) {return nowk ? d[a].x < d[b].x : d[a].y < d[b].y;}
void build(int &k, int l, int r, int d)
{
	if (l > r)return;
	int mid = (l + r) >> 1; nowk = d;
	nth_element(s + l, s + mid, s + r + 1, my); k = s[mid] + n;
	build(lson, l, mid - 1, k ^ 1); build(rson, mid + 1, r, k ^ 1);
	pushup(k);
}
void ADD(int k, int now)
{
	if (maxx[k] < t[now].l || t[now].r < minx[k] || maxy[k] < t[now].d || t[now].u < miny[k] )return;
	if (t[now].l <= minx[k] && maxx[k] <= t[now].r && t[now].d <= miny[k] && maxy[k] <= t[now].u) {add(t[now].p, k, t[now].t); return;}
	if (t[now].l <= d[k - n].x && d[k - n].x <= t[now].r && t[now].d <= d[k - n].y && d[k - n].y <= t[now].u)add(t[now].p, k - n, t[now].t);
	if (lson)ADD(lson, now); if (rson)ADD(rson, now);
}
void DIJ()
{
	int x;
	memset(dis, 0x3f, sizeof(dis));
	q.push(pr(0, 1)); dis[1] = 0;
	while (!q.empty())
	{
		x = q.top().second; q.pop();
		if (vis[x])continue; vis[x] = 1;
		for (int i = head[x]; i; i = nt[i])
			if (dis[to[i]] > dis[x] + val[i])
			{
				dis[to[i]] = dis[x] + val[i];
				q.push(pr(-dis[to[i]], to[i]));
			}
	}
}
int main()
{
	cin >> n >> m >> w >> h;
	for (int i = 1; i <= n; ++i)d[i].x = read(), d[i].y = read(), d[i].id = i, s[i] = i;
	build(root, 1, n, 0);
	for (int i = 1; i <= m; ++i)
	{
	        t[i].p = read(), t[i].t = read(), t[i].l = read(), t[i].r = read(), t[i].d = read(), t[i].u = read();
		ADD(root, i);
	}
	DIJ();
	for (int i = 2; i <= n; ++i)printf("%d\n", dis[i]);
	return 0;
}

被卡空间.jpg。边数太多了，我们无法把边全都建出来，又因为 \(Dij\) 的特性，一个点只会遍历一次和它相连的边，所以我们只需要用到边的时候再去找就行。

根据实现60~80不等

#include
#include
#include
#include
#include
#include
#define lson ch[k][0]
#define rson ch[k][1]
#define pr pair
using namespace std;
int n, m, w, h, num, root, nowk, now;
const int N = 140010, M = 150010;
int dis[N], vis[N], s[N], ch[N][2], minx[N], miny[N], maxx[N], maxy[N];
priority_queueq;
vectorv[N];
struct dian {int x, y;} d[N];
struct tiao {int p, t, l, r, d, u;} t[M];
inline int read()
{
	int res = 0; char ch = getchar(); bool XX = false;
	for (; !isdigit(ch); ch = getchar())(ch == '-') && (XX = true);
	for (; isdigit(ch); ch = getchar())res = (res << 3) + (res << 1) + (ch ^ 48);
	return XX ? -res : res;
}
inline void pushup(int k)
{
	minx[k] = maxx[k] = d[k - n].x; miny[k] = maxy[k] = d[k - n].y;
	if (lson)minx[k] = min(minx[k], minx[lson]), maxx[k] = max(maxx[k], maxx[lson]), miny[k] = min(miny[k], miny[lson]), maxy[k] = max(maxy[k], maxy[lson]);
	if (rson)minx[k] = min(minx[k], minx[rson]), maxx[k] = max(maxx[k], maxx[rson]), miny[k] = min(miny[k], miny[rson]), maxy[k] = max(maxy[k], maxy[rson]);
}
inline int my(int a, int b) {return nowk ? d[a].x < d[b].x : d[a].y < d[b].y;}
void build(int &k, int l, int r, int d)
{
	if (l > r)return;
	int mid = (l + r) >> 1; nowk = d;
	nth_element(s + l, s + mid, s + r + 1, my); k = s[mid] + n;
	build(lson, l, mid - 1, k ^ 1); build(rson, mid + 1, r, k ^ 1);
	pushup(k);
}
inline void geng(int y, int val)
{
	if (dis[y] > val)dis[y] = val, q.push(pr(-dis[y], y));
}
void ADD(int k)
{
	if (vis[k])return;
	if (maxx[k] < t[now].l || t[now].r < minx[k] || maxy[k] < t[now].d || t[now].u < miny[k] )return;
	if (t[now].l <= minx[k] && maxx[k] <= t[now].r && t[now].d <= miny[k] && maxy[k] <= t[now].u) {geng(k, dis[t[now].p] + t[now].t); return;}
	if (t[now].l <= d[k - n].x && d[k - n].x <= t[now].r && t[now].d <= d[k - n].y && d[k - n].y <= t[now].u)geng(k - n, dis[t[now].p] + t[now].t);
	if (lson)ADD(lson); if (rson)ADD(rson);
}
inline void DIJ()
{
	int x;
	memset(dis, 0x3f, sizeof(dis));
	q.push(pr(0, 1)); dis[1] = 0;
	while (!q.empty())
	{
		x = q.top().second; q.pop();
		if (vis[x])continue; vis[x] = 1;
		if (x <= n)
		{
			for (int i = 0, siz = v[x].size(); i < siz; ++i)now = v[x][i], ADD(root);
		}
		else
		{
			if (ch[x][0])geng(ch[x][0], dis[x]);
			if (ch[x][1])geng(ch[x][1], dis[x]);
			geng(x - n, dis[x]);
		}
	}
}
signed main()
{
	cin >> n >> m >> w >> h;
	for (int i = 1; i <= n; ++i)d[i].x = read(), d[i].y = read(), s[i] = i;
	build(root, 1, n, 0);
	for (int i = 1; i <= m; ++i)
		t[i].p = read(), t[i].t = read(), t[i].l = read(), t[i].r = read(), t[i].d = read(), t[i].u = read(), v[t[i].p].push_back(i);
	DIJ();
	for (int i = 2; i <= n; ++i)printf("%d\n", dis[i]);
	return 0;
}

我们发现 \(Dij\) 每次是 \(1\) .取出dis最小的点 \(2\) .更新和它相连的点 \(3\).删去该点。

这些 \(KDtree\) 本身都可以完成，直接在 \(KDtree\) 上维护就行了。

\(shu\) 里的变量

\(p,val,id,vis\) ：该点对应的点的坐标， \(dis\) ，编号，是否取出过

\(l,r,mn,mx,tag\) :区间的坐标最大/小值， \(dis\) 的最大/小值，对区间打的标记。

100分

#include
#include
#include
#include
#define lson tr[k].ls
#define rson tr[k].rs
using namespace std;
int n, m, w, h, p, t, l, r, d, u, root, nowk, cnt;
const int N = 70010, inf = 0x3f3f3f3f;
int s[N], dis[N];
struct dian {int x, y;} di[N];
struct bian {dian l, r; int dis;};
struct shu {dian p, l, r; int ls, rs, mn, mx, val, id, tag, vis;} tr[N];
vectorv[N];
inline int read()
{
	int res = 0; char ch = getchar(); bool XX = false;
	for (; !isdigit(ch); ch = getchar())(ch == '-') && (XX = true);
	for (; isdigit(ch); ch = getchar())res = (res << 3) + (res << 1) + (ch ^ 48);
	return XX ? -res : res;
}
void pushup(int k)
{
	if (tr[k].vis)tr[k].l = (dian) {inf, inf}, tr[k].r = (dian) { -inf, -inf};
	else tr[k].l = tr[k].r = tr[k].p;
	if (lson)tr[k].l.x = min(tr[k].l.x, tr[lson].l.x), tr[k].l.y = min(tr[k].l.y, tr[lson].l.y), tr[k].r.x = max(tr[k].r.x, tr[lson].r.x), tr[k].r.y = max(tr[k].r.y, tr[lson].r.y);
	if (rson)tr[k].l.x = min(tr[k].l.x, tr[rson].l.x), tr[k].l.y = min(tr[k].l.y, tr[rson].l.y), tr[k].r.x = max(tr[k].r.x, tr[rson].r.x), tr[k].r.y = max(tr[k].r.y, tr[rson].r.y);
}
void upd(int k)
{
	if (tr[k].vis)tr[k].mn = inf, tr[k].mx = -inf;
	else tr[k].mn = tr[k].mx = tr[k].val;
	if (lson)tr[k].mn = min(tr[k].mn, tr[lson].mn), tr[k].mx = max(tr[k].mx, tr[lson].mx);
	if (rson)tr[k].mn = min(tr[k].mn, tr[rson].mn), tr[k].mx = max(tr[k].mx, tr[rson].mx);
}
int my(int a, int b)
{
	return nowk ? di[a].x < di[b].x : di[a].y < di[b].y;
}
void build(int &k, int l, int r, int now)
{
	if (l > r)return; k = ++cnt; nowk = now;
	int mid = (l + r) >> 1;
	nth_element(s + l, s + mid, s + r + 1, my);
	tr[k].id = s[mid]; tr[k].p = di[s[mid]]; tr[k].val = tr[k].tag = inf;
	if (tr[k].id == 1)tr[k].val = 0;
	build(lson, l, mid - 1, now ^ 1); build(rson, mid + 1, r, now ^ 1);
	pushup(k); upd(k);
}
void work(int k, int v)
{
	if (v < tr[k].mx && v < tr[k].tag)
	{
		tr[k].mx = tr[k].tag = v; tr[k].mn = min(tr[k].mn, v);
		if (!tr[k].vis)tr[k].val = min(tr[k].val, v);
	}
}
void pushdown(int k)
{
	if (tr[k].tag == inf)return;
	if (lson)work(lson, tr[k].tag); if (rson)work(rson, tr[k].tag);
	tr[k].tag = inf;
}
int find(int k, int v)
{
	int res;
	pushdown(k);
	if (!tr[k].vis && v == tr[k].val) {tr[k].vis = 1; pushup(k); upd(k); return k;}
	if (lson && tr[lson].mn == v)res = find(lson, v);
	else res = find(rson, v);
	pushup(k); upd(k);
	return res;
}
void change(int k, int v, dian l, dian r)
{
	pushdown(k);
	if (v >= tr[k].mx)return;
	if (r.x < tr[k].l.x || tr[k].r.x < l.x || r.y < tr[k].l.y || tr[k].r.y < l.y)return;
	if (l.x <= tr[k].l.x && tr[k].r.x <= r.x && l.y <= tr[k].l.y && tr[k].r.y <= r.y) {work(k, v); return;}
	if (!tr[k].vis && l.x <= tr[k].p.x && tr[k].p.x <= r.x && l.y <= tr[k].p.y && tr[k].p.y <= r.y)tr[k].val = min(tr[k].val, v);
	if (lson)change(lson, v, l, r); if (rson)change(rson, v, l, r);
	pushup(k); upd(k);
}
signed main()
{
	cin >> n >> m >> w >> h;
	for (int i = 1; i <= n; ++i)di[i].x = read(), di[i].y = read(), s[i] = i;
	for (int i = 1; i <= m; ++i)
	{
		p = read(), t = read(), l = read(), r = read(), d = read(), u = read();
		v[p].push_back((bian) {(dian) {l, d}, (dian) {r, u}, t});
	}
	build(root, 1, n, 0);
	for (int i = 1, pos, x; i <= n; ++i)
	{
		x = tr[pos = find(root, tr[root].mn)].id; dis[x] = tr[pos].val;
		for (int j = 0, siz = v[x].size(); j < siz; ++j)change(root, dis[x] + v[x][j].dis, v[x][j].l, v[x][j].r);
	}
	for (int i = 2; i <= n; ++i)printf("%d\n", dis[i]);
	return 0;
}