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
|
#include <bits/stdc++.h>
using namespace std;
#define loop(i,L,R) for (int i=L; i<R; i++)
#define left(p) ((p) << 1)
#define right(p) (((p) << 1) + 1)
char s[200001];
const int oo = INT_MAX / 2;
struct automaton {
int m[5][5]; // 用一個 5 * 5 的矩陣代表一台自動機
automaton (char c = 0) {
loop(i,0,5) loop(j,i,5)
m[i][j] = (i != j) * oo; // no cost if there is no movement
switch (c) {
case '2': m[0][1] = 0; m[0][0] = 1; break;
case '0': m[1][2] = 0; m[1][1] = 1; break;
case '1': m[2][3] = 0; m[2][2] = 1; break;
case '7': m[3][4] = 0; m[3][3] = 1; break;
case '6': m[3][3] = 1; m[4][4] = 1; break;
}
}
automaton operator*(const automaton& o) const {
automaton ans;
loop(i,0,5) loop(j,i,5) { // 0 <= i <= j < 5
ans.m[i][j] = oo;
loop(k,i,j+1) ans.m[i][j] = min(ans.m[i][j], m[i][k] + o.m[k][j]);
}
return ans;
}
};
struct segtree {
vector<automaton> nodes; // 每個節點都儲存一台自動機，節點號碼從 1 開始，才能遵循 LeftChild * 2、RightChild * 2 + 1 原則
automaton build(int p, int l, int r) { // 求出區間 [l-r] 的答案並儲存在號碼 p 的節點
assert(l <= r); // 從中間剖分的過程中，左索引值不可能超過右索引值
if (l == r) return nodes[p] = automaton(s[l]); // 區間為單點元素時只得自行計算出答案
int m = (l + r) >> 1; // 取中點
auto a1 = build(left(p), l, m); // 求出區間 [l-m] 的答案並儲存在號碼 2 * p 的節點
auto a2 = build(right(p), m+1, r); // 求出區間 [(m+1)-r] 的答案並儲存在號碼 2 * p + 1 的節點
return nodes[p] = a1 * a2; // 合併左右子樹的兩個答案以求出自己的答案，並存進節點中
}
int N; // 整串序列的長度
segtree(int n): nodes(n << 2) { // 欲查詢長度為 N 的序列答案所對應到的線段樹最多需要 4N - 1 個節點
N = n; build(1, 1, N); // https://cp-algorithms.com/data_structures/segment_tree.html
}
int L, R; // 用於 query 和 recursive，表示欲查詢區間為 [L-R]
automaton query(int l, int r) {
L = l; R = r; assert(L <= R); // 欲查詢區間 [L-R] 在計算過程中不會改變
return rec(1, 1, N); // 給定大區間 [1-N] 內所有子區間的已知資料，如何求出恰為 [L-R] 區間的答案？
}
// 給定過程中已經有答案的節點區間 [l-r]，最後會回傳此區間和欲查詢區間 [L-R] 交集之後的答案，注意這三個數字本應與 build 過程中所設定的一致
automaton rec(int p, int l, int r) { // assert(l <= r); // "rec" stands for "recursive"
if (r < L || R < l) return automaton(); // 如果節點區間與欲查詢區間沒有重疊，則希望此答案為乘法單位元素 (相乘之後不影響其他區間的答案)
if (L <= l && r <= R) return nodes[p]; // 如果節點區間已經被完整包覆在欲查詢區間之內，則直接貢獻答案 (停止繼續遞迴)
// 如果節點區間和欲查詢區間僅部分重疊，則把自己這個節點區間再切成兩半，分別繼續做 rec
int m = (l + r) >> 1; // 取中點，注意到下面的 left(p), l, m 和 right(p), m+1, r 的 pattern 會與 build 的過程完全相同
return rec(left(p), l, m) * rec(right(p), m+1, r); // pseudo multiplication
}
};
int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
int n, q;
scanf("%d%d", &n, &q);
scanf("%s", s+1);
segtree st(n);
loop(i,0,q) {
int a, b;
scanf("%d%d", &a, &b);
int ans = st.query(a, b).m[0][4];
if (ans == oo) ans = -1;
cout << ans << endl;
}
return 0;
}
|
alan23273850 的刷題筆記
