@loj

目录

• @description@
• @solution@
• @accepted code@
• @details@

---

@description@

跳蚤国有 n 座城市，分别编号为 1~n，1 号城市为首都。所有城市分布在一个 w×h 范围的网格上。每座城市都有一个整数坐标 (x,y)(1<=x<=w, 1<=y<=h)，不同城市的坐标不相同。

在跳蚤国中共有 m 个弹跳装置，分别编号为 1~m，其中 i 号弹跳装置位于 pi 号城市，并具有参数 ti,Li,Ri,Di,Ui。利用该弹跳装置，跳蚤可花费 ti(ti>0) 个单位时间，从 pi 号城市跳至坐标满足 Li<=x<=Ri, Di<=y<=Ui(1<=Li<=Ri<=w, 1<=Di<=Ui<=h) 的任意一座城市。需要注意的是，一座城市中可能存在多个弹跳装置，也可能没有弹跳装置。

由于城市间距离较远，跳蚤们必须依靠弹跳装置出行。具体来说，一次出行将经过若干座城市，依次经过的城市的编号可用序列 (a_0,a_1,dots,a_k) 表示；在此次出行中，依次利用的弹跳装置的编号可用序列 (b_1,b_2,...,b_k) 表示。其中每座城市可在序列 ({a_j}) 中出现任意次，每个弹跳装置也可在序列 ({b_j}) 中出现任意次，且满足，对于每个 (j(1leq jleq k))，编号为 (b_j) 的弹跳装置位于城市 (a_{j-1})，且跳蚤能通过该弹跳装置跳至城市 (a_j)。我们称这是一次从城市 (a_0) 到城市 (a_k) 的出行，其进行了 (k) 次弹跳，共花费 (sum_{i=1}^{k}t_{b_i})个单位时间。

现在跳蚤国王想知道，对于跳蚤国除首都（1 号城市）外的每座城市，从首都出发，到达该城市最少需要花费的单位时间。跳蚤国王保证，对每座城市，均存在从首都到它的出行方案。

原题传送门。

@solution@

方法很多，但是如果真的建图跑 dijkstra 就是死路一条。这里选用讲题时所说的KD树做法。

考虑 dijkstra 需要干什么：找到当前未被访问且距离最小的点 x；更新某些点的距离。

相当于二维区域查询 min；二维区域取 min；单点删除。

树套树的空间开支比较大，所以我们使用 KD 树维护。
区域取 min 可以使用类 segment tree beats 的方式优化（存最大值），不过好像对复杂度影响不大。
单点删除采用惰性删除，因为不插入新点所以也不需要重构。

时间复杂度 (O(nsqrt{n}))。

@accepted code@

#include <cstdio>
#include <vector>
#include <cassert>
#include <algorithm>
using namespace std;

const int MAXN = 70000;
const int INF = int(1E9);

struct point{
	int x, y, id;
	friend point min(point a, point b) {return (point) {min(a.x, b.x), min(a.y, b.y)};}
	friend point max(point a, point b) {return (point) {max(a.x, b.x), max(a.y, b.y)};}
}pnt[MAXN + 5];

int DIM;
bool cmp(point a, point b) {
	if( DIM == 0 ) return (a.x == b.x) ? (a.y < b.y) : (a.x < b.x);
	else return (a.y == b.y) ? (a.x < b.x) : (a.y < b.y);
}

namespace KDT{
	struct node{
		point p, bl, br; bool vis;
		int tag, key, mn, mx; node *ch[2];
	}pl[MAXN + 5], *NIL, *ncnt, *root;
	void init() {
		NIL = ncnt = pl, NIL->ch[0] = NIL->ch[1] = NIL;
		NIL->vis = false, NIL->tag = NIL->key = NIL->mn = INF, NIL->mx = 0;
		NIL->bl = (point) {INF, INF}, NIL->br = (point) {-INF, -INF};
	}
	void pushup(node *x) {
		if( x->vis )
			x->mn = NIL->mn, x->mx = NIL->mx, x->bl = NIL->bl, x->br = NIL->br;
		else x->mn = x->mx = x->key, x->bl = x->br = x->p;
		x->mn = min(x->mn, min(x->ch[0]->mn, x->ch[1]->mn)), x->mx = max(x->mx, max(x->ch[0]->mx, x->ch[1]->mx));
		x->bl = min(x->bl, min(x->ch[0]->bl, x->ch[1]->bl)), x->br = max(x->br, max(x->ch[0]->br, x->ch[1]->br));
	}
	node *newnode(point p) {
		node *q = (++ncnt); (*q) = (*NIL);
		q->p = q->bl = q->br = p; return q;
	}
	node *build(point *p, int l, int r, int d) {
		if( l > r ) return NIL;
		DIM = d; int m = (l + r) >> 1;
		nth_element(p + l, p + m, p + r + 1, cmp);
		
		node *x = newnode(p[m]);
		x->ch[0] = build(p, l, m - 1, d ^ 1);
		x->ch[1] = build(p, m + 1, r, d ^ 1);
		pushup(x); return x;
	}
	void addtag(node *x, int k) {
		if( k < x->mx ) {
			x->tag = x->mx = k, x->mn = min(x->mn, k);
			if( !x->vis ) x->key = min(x->key, k);
		}
	}
	void pushdown(node *x) {addtag(x->ch[0], x->tag), addtag(x->ch[1], x->tag);}
	node *get_min(node *x) {
		pushdown(x);
		if( !x->vis && x->key == x->mn ) {
			x->vis = true;
			pushup(x); return x;
		}
		assert(x->ch[0]->mn == x->mn || x->ch[1]->mn == x->mn);
		node *ans = get_min(x->ch[0]->mn == x->mn ? x->ch[0] : x->ch[1]);
		pushup(x); return ans;
	}
	void update(node *x, int lx, int rx, int ly, int ry, int k) {
		if( k >= x->mx || rx < x->bl.x || lx > x->br.x || ry < x->bl.y || ly > x->br.y ) return ;
		if( lx <= x->bl.x && x->br.x <= rx && ly <= x->bl.y && x->br.y <= ry ) {
			addtag(x, k);
			return ;
		}
		if( !x->vis && lx <= x->p.x && x->p.x <= rx && ly <= x->p.y && x->p.y <= ry )
			x->key = min(x->key, k);
		pushdown(x);
		update(x->ch[0], lx, rx, ly, ry, k);
		update(x->ch[1], lx, rx, ly, ry, k);
		pushup(x);
	}
}

struct node{int lx, rx, ly, ry, t;};
vector<node>v[MAXN + 5];

int dist[MAXN + 5];
int main() {
	freopen("jump.in", "r", stdin);
	freopen("jump.out", "w", stdout);
	
	KDT::init(); int n, m, w, h;
	scanf("%d%d%d%d", &n, &m, &w, &h);
	for(int i=1;i<=n;i++)
		scanf("%d%d", &pnt[i].x, &pnt[i].y), pnt[i].id = i;
	for(int i=1,p,t,L,R,D,U;i<=m;i++) {
		scanf("%d%d%d%d%d%d", &p, &t, &L, &R, &D, &U);
		v[p].push_back((node){L, R, D, U, t});
	}
	
	int sx = pnt[1].x, sy = pnt[1].y;
	KDT::root = KDT::build(pnt, 1, n, 0);
	KDT::update(KDT::root, sx, sx, sy, sy, 0);
	for(int i=1;i<=n;i++) {
		KDT::node *x = KDT::get_min(KDT::root);
		dist[x->p.id] = x->key;
		for(unsigned j=0;j<v[x->p.id].size();j++) {
			node p = v[x->p.id][j];
			KDT::update(KDT::root, p.lx, p.rx, p.ly, p.ry, dist[x->p.id] + p.t);
		}
	}
	for(int i=2;i<=n;i++) printf("%d
", dist[i]);
}

@details@

“KD树？那玩意儿谁用谁被卡。”

主要是更新+存储一下自己的KD树模板