IOI 2019 天桥 题解

First Post:

Last Update:

本题的解题思路其实比较短，发现性质之后就做完了（不过性质证明倒是很长）。不过这个发现性质的过程也是有教育意义的。本文主要记录做题时的心路历程，再说正解做法。

题目链接：https://loj.ac/p/3180

拿到这题之后，前两个 Subtask 非常简单地就做完了，把所有交点拿出来建图即可。

然后看 ， 全相同，容易发现此时路径不会往回拐，然后切换天桥时肯定选择在第一个能切换的点切换最优，然后当时想的就是不管横向代价，向右扫描线维护走到每个天桥左端点的最短路，然后在加入新桥时用数据结构算出这个答案即可。。

事实上这个做法被数据结构思想带偏了，如果能够一开始还就坚持优化建图 的思路，尝试细化与改进这个性质，就可能可以通向正解。

正解其实基于一个结论：如果没有天桥在 轴上跨过 和 ，当升高高度时，肯定处于目标天桥的左端点；降低高度时，肯定处于起始天桥的右端点。于是我们只用保留每根天桥的端点，以及这些端点的下面最高的一个交点，然后建图跑最短路即可。证明可以阅读其他题解，大概思路是调整法。

如果有跨过 的天桥，找到 表示 两边最靠近 的与该天桥有交的建筑，将天桥拆成 三段即可。跨过 同理。都跨过就拆成五段。然后建图跑最短路就行了。

这说明做题的时候要想明白这个题的 basic idea，也就是基本方向，然后再想明白这个方向上的各类性质与规律，然后形成做法，最后写代码。这些环节的准确率和速度才是我们训练的目标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include <bits/stdc++.h>
using namespace std;
const int N = 1.2e6 + 5;
typedef pair<int,int> pii;
typedef long long ll;
#define FI first
#define SE second
#define mkp make_pair

int n,m,St,Ed;
int X[N],h[N],ph[N],pb[N];
int L[N],R[N],hgt[N];
set<pair<int,int> > bris;

int tot;
long long dis[N];
bool vst[N];
vector<pii> G[N];
vector<int> Bl[N],Br[N];
inline void addedge(int u1,int v1,int w1) {
	// printf("Edge:%d,%d,%d\n",u1,v1,w1);
	G[u1].emplace_back(v1,w1);
	G[v1].emplace_back(u1,w1);
}
map<pii,int> mp;
struct node {
	int id;ll dis;
	node(){}
	node(const int _id,const ll _dis):id(_id),dis(_dis){}
	bool operator < (const node &rhs) const { return dis > rhs.dis;}
};
inline void Dijkstra(int S) {
	for(int i = 1;i <= tot;i++) dis[i] = 1e18,vst[i] = 0;
	priority_queue<node> Q;Q.emplace(S,dis[S] = 0);
	while(!Q.empty()) {
		int x = Q.top().id;Q.pop();
		if(vst[x]) continue;
		vst[x] = true;
		for(auto [y,w] : G[x])
			if(dis[y] > dis[x] + w)
				Q.emplace(y,dis[y] = dis[x] + w);
	}
}

struct SGT {
	int Mn[N << 2],tag[N << 2];
	inline void pushup(int k) { Mn[k] = min(Mn[k << 1],Mn[k << 1 | 1]);}
	inline void Add(int k,int v) { tag[k] += v;Mn[k] += v;}
	inline void pushdown(int k) { if(tag[k]) Add(k << 1,tag[k]),Add(k << 1 | 1,tag[k]),tag[k] = 0;}
	void modify(int k,int l,int r,int x,int y,int v) {
		if(x > y) return;
		if(x <= l && r <= y) return Add(k,v);
		int mid = l + r >> 1;
		pushdown(k);
		if(x <= mid) modify(k << 1,l,mid,x,y,v);
		if(mid < y) modify(k << 1 | 1,mid + 1,r,x,y,v);
		pushup(k);
	}
	int Query(int k,int l,int r,int x,int y) {
		if(x <= l && r <= y) return Mn[k];
		int mid = l + r >> 1;
		pushdown(k);
		if(y <= mid) return Query(k << 1,l,mid,x,y);
		else if(x > mid) return Query(k << 1 | 1,mid + 1,r,x,y);
		else return min(Query(k << 1,l,mid,x,y),Query(k << 1 | 1,mid + 1,r,x,y));
	}
};
SGT T;

vector<pii> pois[4];
vector<int> Mn[4],Mx[4],DD[N];
inline int Getval(int t,int hh,int op) {
	int lef = -1,rig = (int)pois[t].size() - 1;
	while(lef < rig) {
		int mid = lef + rig + 1 >> 1;
		if(pois[t][mid].FI >= hh) lef = mid;
		else rig = mid - 1;
	}
	assert(lef >= 0);
	return op ? Mn[t][lef] : Mx[t][lef];
}
inline void Prework() {
	for(int i = 1;i <= St;i++) pois[0].emplace_back(h[i],i);
	for(int i = St;i <= n;i++) pois[1].emplace_back(h[i],i);
	for(int i = 1;i <= Ed;i++) pois[2].emplace_back(h[i],i);
	for(int i = Ed;i <= n;i++) pois[3].emplace_back(h[i],i);
	for(int t = 0;t < 4;t++) if(pois[t].size()) {
		sort(pois[t].begin(),pois[t].end(),greater<pii>());
		Mn[t].resize(pois[t].size());Mx[t].resize(pois[t].size());
		Mn[t][0] = Mx[t][0] = pois[t][0].SE;
		for(int i = 1;i < pois[t].size();i++) 
			Mn[t][i] = min(Mn[t][i - 1],pois[t][i].SE),
			Mx[t][i] = max(Mx[t][i - 1],pois[t][i].SE);
	}
	for(int i = 1,cnt = m;i <= cnt;i++) {
		if(R[i] < St || L[i] > Ed) continue;
		if(St < L[i] && R[i] < Ed) continue;
		int X,Y;
		if(L[i] <= St && Ed <= R[i]) {
			X = Getval(0,hgt[i],0);Y = Getval(1,hgt[i],1);
			DD[X].push_back(hgt[i]);DD[Y].push_back(hgt[i]);
			X = Getval(2,hgt[i],0);Y = Getval(3,hgt[i],1);
			DD[X].push_back(hgt[i]);DD[Y].push_back(hgt[i]);
		} else if(L[i] <= St && St <= R[i]) {
			X = Getval(0,hgt[i],0);
			Y = Getval(1,hgt[i],1);
			DD[X].push_back(hgt[i]);DD[Y].push_back(hgt[i]);
		} else {
			X = Getval(2,hgt[i],0);
			Y = Getval(3,hgt[i],1);
			DD[X].push_back(hgt[i]);DD[Y].push_back(hgt[i]);
		}
	}
}
int main() {
	// freopen("tmp.in","r",stdin);
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
		cin >> X[i] >> h[i],ph[i] = i;
	sort(ph + 1,ph + n + 1,[&](const int &x,const int &y) { return h[x] < h[y];});
	for(int i = 1;i <= m;i++) {
		cin >> L[i] >> R[i] >> hgt[i];
		++L[i];++R[i];
	}
	cin >> St >> Ed;++St;++Ed;
	if(St > Ed) swap(St,Ed);
	Prework();
	for(int i = 1;i <= m;i++)
		Bl[L[i]].push_back(i),Br[R[i]].push_back(i),pb[i] = i;
	sort(pb + 1,pb + m + 1,[&](const int &x,const int &y) { return hgt[x] < hgt[y];});
	for(int i = 1;i <= n;i++) {
		vector<int> ds = DD[i],d2;
		for(auto j : Bl[i]) ds.push_back(hgt[j]);
		for(auto j : Br[i]) ds.push_back(hgt[j]);
		if(i == St || i == Ed) ds.push_back(0);
		sort(ds.begin(),ds.end());
		ds.erase(unique(ds.begin(),ds.end()),ds.end());
		for(auto j : Bl[i]) bris.emplace(hgt[j],j);
		for(auto j : Br[i - 1]) bris.erase(mkp(hgt[j],j));
		d2 = ds;
		for(auto j : ds) {
			auto it = bris.lower_bound(mkp(j,0));
			if(it != bris.begin()) d2.push_back(prev(it) -> FI);
		}
		ds = d2;
		sort(ds.begin(),ds.end());
		ds.erase(unique(ds.begin(),ds.end()),ds.end());
		for(int j = 0;j < ds.size();++j) {
			int u = ds[j];mp[mkp(i,u)] = ++tot;
			if(j > 0) addedge(tot - 1,tot,ds[j] - ds[j - 1]);
		}
	}
	vector<pii> Ts;
	for(auto it : mp) Ts.push_back(it.FI);
	sort(Ts.begin(),Ts.end(),[&](const pii &x,const pii &y) { return x.SE != y.SE ? x.SE < y.SE : x.FI < y.FI;});
	for(int l = 0,r,l2 = 1,r2 = 0;l < Ts.size();l = r + 1) {
		r = l;
		while(r + 1 < Ts.size() && Ts[r + 1].SE == Ts[l].SE) ++r;
		while(l2 <= m && hgt[pb[l2]] < Ts[l].SE) ++l2;
		while(r2 + 1 <= m && hgt[pb[r2 + 1]] <= Ts[l].SE) ++r2;
		for(int i = l2;i <= r2;i++)
			T.modify(1,1,n,L[pb[i]],R[pb[i]] - 1,1);
		for(int i = l + 1;i <= r;i++)
			if(T.Query(1,1,n,Ts[i - 1].FI,Ts[i].FI - 1)) 
				addedge(mp[Ts[i - 1]],mp[Ts[i]],X[Ts[i].FI] - X[Ts[i - 1].FI]);
		for(int i = l2;i <= r2;i++) 
			T.modify(1,1,n,L[pb[i]],R[pb[i]] - 1,-1);
	}
	Dijkstra(mp[mkp(St,0)]);
	ll ans = dis[mp[mkp(Ed,0)]];
	if(ans >= 1e18) puts("-1");
	else printf("%lld\n",ans);
	return 0;
}	

// start: 2023.12.28 15:40
// finish coding: 2023.12.28 16:08
// finish debugging: 2023.12.28 17:28
≡