LOJ3665 铁路旅行 题解

First Post:

Last Update:

此题拓宽了我对倍增的理解。倍增并不一定只适用于状态数可以存储的情况。

设 表示位置 能一步走到的区间。

首先考虑只往右跳的 Subtask 怎么做。暴力是维护一个当前拓展到的右端点 。每次拓展时选择 中 最大的值，将 赋值为这个值。

这个算法难以优化之处在于信息与 有关，难以预处理什么东西。

但你发现，设 中 最大的位置为 ，那么 中的数就没有影响了，也就是说，下一次查找时不需要从 开始找，直接查找 中的值往后转移即可。假设转移到 ，下一次又可以在 中查询并转移。整个过程中，我们不记录之前的 ，而是记录这个位置 。

此时拓展过程就和 无关了，且每个位置的后继是唯一的，倍增加速跳后继的过程即可。

回到原问题，此时两端都可以拓展，那么我们记录两个值 和 ，一次拓展就是在 和 中找到 最小的位置 ，将 赋值为 。 同理。

我之前一直想着把每对 的后继状态都算出来，其实根本没有必要。因为 和 对后继状态的贡献是分别计算的，只是到最后再合并，所以完全可以只记录每个位置 ，跳了 步后的 和 ，这是可以转移的。

所以本题可以做到 ，不懂为什么 要出 。

部分细节在代码里。

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
const int N = 1e5 + 5,M = 2e5 + 5,Lg = 18;
int n,m,K,Q;
int A[M],B[M];
int tl[N],tr[N];
vector<int> ScanLine[N];
multiset<int> Scan; // 用以区间 ckMax
int STL[Lg][N],STR[Lg][N];
inline int MinL(int x,int y) { return tl[x] < tl[y] ? x : y;}
inline int MaxR(int x,int y) { return tr[x] > tr[y] ? x : y;}
int lg[N];
inline int QminL(int l,int r) {
	int k = lg[r - l + 1];
	return MinL(STL[k][l],STL[k][r-(1<<k)+1]);
}
inline int QmaxR(int l,int r) {
	int k = lg[r - l + 1];
	return MaxR(STR[k][l],STR[k][r-(1<<k)+1]);
}
inline void init() {
	read(n);read(K);
	read(m);
	for(int i = 1;i <= m;i++) 
		read(A[i]),read(B[i]);
	for(int i = 1;i <= m;i++)
		if(A[i] < B[i]) 
			ScanLine[A[i]].push_back(B[i]),
			ScanLine[min(A[i] + K - 1,B[i] - 1) + 1].push_back(-B[i]);
	for(int i = 1;i <= n;i++) {
		for(auto j : ScanLine[i])
			if(j > 0) Scan.insert(j);
			else Scan.erase(Scan.find(-j));
		tr[i] = i;
		if(Scan.size()) tr[i] = max(tr[i],*Scan.rbegin());
		
		ScanLine[i].clear();
	}
	Scan.clear();
	for(int i = 1;i <= m;i++)
		if(A[i] > B[i]) 
			ScanLine[max(A[i] - K + 1,B[i] + 1)].push_back(B[i]),
			ScanLine[A[i] + 1].push_back(-B[i]);
	for(int i = 1;i <= n;i++) {
		for(auto j : ScanLine[i])
			if(j > 0) Scan.insert(j);
			else Scan.erase(Scan.find(-j));
		tl[i] = i;
		if(Scan.size()) tl[i] = min(tl[i],*Scan.begin());
		
		ScanLine[i].clear();
	}
	lg[0] = -1;
	for(int i = 1;i <= n;i++) STL[0][i] = STR[0][i] = i,lg[i] = lg[i >> 1] + 1;
	for(int j = 1;j < Lg;j++)
		for(int i = 1;i + (1 << j) - 1 <= n;i++)
			STL[j][i] = MinL(STL[j - 1][i],STL[j - 1][i + (1 << j - 1)]),
			STR[j][i] = MaxR(STR[j - 1][i],STR[j - 1][i + (1 << j - 1)]);
}	
int goL[Lg][N],goR[Lg][N];
inline void initjump() {
	for(int i = 1;i <= n;i++) 
		goL[0][i] = QminL(tl[i],tr[i]),goR[0][i] = QmaxR(tl[i],tr[i]),assert(tl[i] <= tr[i]);
	for(int j = 1;j < Lg;j++)
		for(int i = 1;i <= n;i++) {
			int l1 = goL[j - 1][i],r1 = goR[j - 1][i];
			int l2 = MinL(goL[j - 1][l1],goL[j - 1][r1]);
			int r2 = MaxR(goR[j - 1][l1],goR[j - 1][r1]);
			goL[j][i] = l2;goR[j][i] = r2;
			assert(1 <= l2 && l2 <= n);
			assert(1 <= r2 && r2 <= n);
		}
}
inline int Jump(int S,int T) {
	int l = S,r = S;
	int ans = 0;
	for(int i = Lg - 1;i >= 0;i--) {
		int i1 = MinL(goL[i][l],goL[i][r]);
		int i2 = MaxR(goR[i][l],goR[i][r]);
		if(tl[i1] > T || tr[i2] < T)
			ans |= (1 << i),l = i1,r = i2;
	}
	if(tl[MinL(l,r)] <= T && T <= tr[MaxR(l,r)]) return ans + 1;
	int i1 = MinL(goL[0][l],goL[0][r]),i2 = MaxR(goR[0][l],goR[0][r]);
	l = i1;r = i2;++ans;

    if(tl[MinL(l,r)] > T || tr[MaxR(l,r)] < T) return -1;
	return ans + 1;
}
int main() {
	init();
	initjump();
	read(Q);
	for(int _ = 1;_ <= Q;_++) {
		int s,t;
		read(s);read(t);
		write(Jump(s,t));
	}
	return 0;
}
≡