解題區/解題區 - Zerojudge

動態幾何 史蒂芙的泡泡 (解法 2)

題目描述

在處理完數以百計的政事後，受盡折磨的史蒂芙，打算回家好好地休息。 拖著疲倦的身軀，再也無法再容納任何一點複雜計算。從王宮走回寢居的路上， 發現身邊所見的事物都不再圓滑，看起來就像是粗糙的幾何多邊形構成的一切。

打算享受著泡泡浴的史蒂芙，看著眼前的多邊形泡泡，失去原本應有的色澤，那透涼的心境更蒙上了一層灰影

「為什麼是我呢？」感嘆道

伸出手戳著眼前的泡泡，卻飄了過去

「區區的泡泡也跟我作對，嗚嗚」

將一個泡泡視為一個簡單多邊形 $A$，方便起見用一個序列 $a_0, a_1, ..., a_{n-1}$ 表示多邊形 $A$ 的每一個頂點，則會有 $n$ 個線段 $\overline{a_0 a_1}, \overline{a_1 a_2}, \cdots, \overline{a_{n-1} a_0}$。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
5 14
0 0
10 0 
10 10
0 10
5 5
1 0 0
1 1 0
1 2 1
1 3 2
3 5.5 5
3 10 -1
3 10 5
1 4 1
3 5.5 5
3 10 -1
3 10 5
2 3
3 5 7.5
3 5 2.5

Sample Output

1
2
3
4
5
6
7
8
1
0
0
0
0
0
0
1

Solution

參閱 動態幾何 史蒂芙的泡泡 (解法 1)

相較於先前的解法 $\mathcal{O}(\log n) - \mathcal{O}(\ast \sqrt{n})$，相當不穩定的嵌套 KD-BRH 的解法，實際上如果單純針對這一題，可以拋開 region search 的操作，只有完全的詢問點是否在多邊形內部，則可以做到 $\mathcal{O}(\log^2 n)$。

如同一般的射線法，對詢問點拉出無限延長的線，找到與多邊形的邊相交個數。如果單純把每一條邊拿出來看，最暴力的複雜度為 $\mathcal{O}(n)$，現在要減少查閱的邊數，且透過 rank tree 在 $\mathcal{O}(\log n)$ 累計相交數量。

由於給定的座標不需要動態，則著手離散化 $X = x_0, x_1, \cdots, x_n$，線段樹中的每一個點 $u$ 維護一個 rank tree，把包含者個區段 $[x_l, x_r]$ 的線段通通放入，且保證放入的線段彼此之間不相交 (除了兩端點)。如此一來，當詢問一個點，需要探訪 $\mathcal{O}(\log n)$ 個節點，每個節點 $u$ 需要 $\mathcal{O}(\log n)$ 時間來計算相交數量，最後詢問的複雜度為 $\mathcal{O}(\log^2 n)$。同理，修改點的操作也會在 $\mathcal{O}(\log^2 n)$。

實作時，特別注意到與射線方向相同的線段不予處理，按照下面的寫法則是不處理垂直的線段，一來是射線法也不會去計算，二來是線段樹劃分的時候會造成一些邊界問題，由於我們對於點離散，父節點 $[x_l, x_r]$，左右子樹控制的分別為 $[x_l, x_\text{mid}]$、$[x_\text{mid}, x_r]$，劃分時會共用中間點。

即使有了上述的概念來解題，我們仍需要維護 rope data structrue 來維護節點的相鄰關係，可以自己實作任何的 binary tree 來達到 $\mathcal{O}(\log n)$，這裡採用 splay tree 示範。

接下來介紹內建黑魔法 PBDS (policy-based data structure) 和 rope。很多人都提及到這些非正式的 STL 函式庫，只有在 gcc/g++ 裡面才有附錄，如果是 clang 等其他編譯器可能是沒有辦法的。所以上傳相關代碼要看 OJ 是否採用純正的 gcc/g++。

參考資料：

PBDS 比較常用在 rank tree 和 heap，由於代碼量非常多，用內建防止 code length exceed limitation 的出現，也不妨是個好辦法。用 rank tree 的每一個詢問操作皆在 $\mathcal{O}(\log n)$，而 heap 選擇 thin heap 或 pairing heap，除了 pop 操作外，皆為 $\mathcal{O}(1)$，在對最短路徑問題上別有優勢。

而這一題不太適用 SGI rope，原因在於雖為 $\mathcal{O}(\log n)$ 操作，但它原本就為了仿作 string 而強迫變成可持久化的引數結構，導致每一個操作需要額外的開銷來減少內存使用。由於此題經常在單一元素上操作，SGI rope 對於單一元素效能不彰，以造成嚴重的逾時。

這裡仍提及和示範這些概念的資料結構，哪天正式編入標準函式庫，想必效能問題都已解決。

  • KD BRH AC(0.2s, 10 MB)
  • PBDS + SPLAY AC(0.3s, 38 MB)
  • PBDS + SGI rope AC(0.5s, 41 MB)
    本機 MINGW gcc 4.9 c++ 11 編譯完運行最大的測資需要 20 倍慢於其他寫法，但是上傳到 ZJ 的 gcc 7 又追回去了。於是下載 CYGWIN gcc 7 測試結果與 ZJ 運行結果相當，對於需要調適的人，建議在新版上測試。

用 splay tree 模擬 rope 的時候，會遇到循序非遞減的走訪，這時候若不斷地旋轉至根，會在之後的操作造成退化，常數稍微大一點，雖然在迭代過程中造就好的快取效能，很快地在 $\mathcal{O}(1)$ 訪問到相鄰的節點，卻在下一次的插入/刪除操作中變慢。一些變異的版本中，如只在插入/刪除操作中旋轉至根，在查找操作中不旋轉，或者限制旋轉的深度。雖然有一些特別的退化操作，splay 仍舊是某些 OS 場景中使用的資料結構，現實總是很特別的。

In 2000, Danny Sleator and Robert Tarjan won the ACM Kanellakis Theory and Practice Award for their papers on splay trees and amortized analysis. Splay trees are used in Windows NT (in the virtual memory, networking, and file system code), the gcc compiler and GNU C++ library, the sed string editor, Fore Systems network routers, the most popular implementation of Unix malloc, Linux loadable kernel modules, and in much other software.

PBDS + SPLAY

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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
struct Mesh {
static const int MAXN = 1e5 + 5;
    int pt[MAXN][2];
    vector<int> X;
    void read(int n) {
        for (int i = 0; i < n; i++)
            scanf("%d %d", &pt[i][0], &pt[i][1]);
        X.clear(); X.reserve(n);
        for (int i = 0; i < n; i++)
            X.push_back(pt[i][0]);
        sort(X.begin(), X.end());
        X.erase(unique(X.begin(), X.end()), X.end());
    }
} mesh;
class SplayTree {
public:
    struct Node {
        Node *ch[2], *fa;
        int size; int data;
        Node() {
            ch[0] = ch[1] = fa = NULL;
            size = 1;
        }
        bool is_root() {
            return fa->ch[0] != this && fa->ch[1] != this;
        }
    };
    Node *root, *EMPTY;
    void pushdown(Node *u) {}
    void pushup(Node *u) {
        if (u->ch[0] != EMPTY)	pushdown(u->ch[0]);
        if (u->ch[1] != EMPTY)	pushdown(u->ch[1]);
        u->size = 1 + u->ch[0]->size + u->ch[1]->size;
    }
    void setch(Node *p, Node *u, int i) {
        if (p != EMPTY)	p->ch[i] = u;
        if (u != EMPTY)	u->fa = p;
    }
    SplayTree() {
        EMPTY = new Node();
        EMPTY->fa = EMPTY->ch[0] = EMPTY->ch[1] = EMPTY;
        EMPTY->size = 0;
    }
    void init() {
        root = EMPTY;
    }
    Node* newNode() {
        Node *u = new Node();
        u->fa = u->ch[0] = u->ch[1] = EMPTY;
        return u;
    }
    void rotate(Node *x) {
        Node *y;
        int d;
        y = x->fa, d = y->ch[1] == x ? 1 : 0;
        x->ch[d^1]->fa = y, y->ch[d] = x->ch[d^1];
        x->ch[d^1] = y;
        if (!y->is_root())
            y->fa->ch[y->fa->ch[1] == y] = x;
        x->fa = y->fa, y->fa = x;
        pushup(y);
    }
    void deal(Node *x) {
        if (!x->is_root())	deal(x->fa);
        pushdown(x);
    }
    void splay(Node *x, Node *below) {
        if (x == EMPTY)	return ;
        Node *y, *z;
        deal(x);
        while (!x->is_root() && x->fa != below) {
            y = x->fa, z = y->fa;
            if (!y->is_root() && y->fa != below) {
                if (y->ch[0] == x ^ z->ch[0] == y)
                    rotate(x);
                else
                    rotate(y);
            }
            rotate(x);
        }
        pushup(x);
        if (x->fa == EMPTY)	root = x;
    }
    Node* prevNode(Node *u) {
        splay(u, EMPTY);
        return maxNode(u->ch[0]);
    }
    Node* nextNode(Node *u) {
        splay(u, EMPTY);
        return minNode(u->ch[1]);
    }
    Node* minNode(Node *u) {
        Node *p = u->fa;
        for (; pushdown(u), u->ch[0] != EMPTY; u = u->ch[0]);
        splay(u, p);
        return u;
    }
    Node* maxNode(Node *u) {
        Node *p = u->fa;
        for (; pushdown(u), u->ch[1] != EMPTY; u = u->ch[1]);
        splay(u, p);
        return u;
    }
    Node* findPos(int pos) { // [0...]
        for (Node *u = root; u != EMPTY;) {
            pushdown(u);
            int t = u->ch[0]->size;
            if (t == pos) {
                splay(u, EMPTY);
                return u;
            }
            if (t > pos)
                u = u->ch[0];
            else
                u = u->ch[1], pos -= t + 1;
        }
        return EMPTY;
    }
    tuple<int, int, int> insert(int data, int pos) {	// make [pos] = data
        Node *p, *q = findPos(pos);
        Node *x = newNode(); x->data = data;
        if (q == EMPTY) {
            p = maxNode(root), splay(p, EMPTY);
            setch(x, p, 0);
            splay(x, EMPTY);
        } else {
            splay(q, EMPTY), p = q->ch[0];
            setch(x, p, 0), setch(x, q, 1);
            setch(q, EMPTY, 0);
            splay(q, EMPTY);
            p = prevNode(x);
        }
        if (p == EMPTY)	p = maxNode(root);
        if (q == EMPTY)	q = minNode(root);
        return make_tuple(p->data, data, q->data);
    }
    tuple<int, int, int> remove(int pos) {
        Node *x = findPos(pos), *p, *q;
        p = prevNode(x), q = nextNode(x);
        if (p != EMPTY && q != EMPTY) {
            setch(p, q, 1);
            p->fa = EMPTY, splay(q, EMPTY);
        } else if (p != EMPTY) {
            p->fa = EMPTY, root = p;
        } else {
            q->fa = EMPTY, root = q;
        }
        int del = x->data;
        delete x;
        if (p == EMPTY)	p = maxNode(root);
        if (q == EMPTY)	q = minNode(root);
        return make_tuple(p->data, del, q->data);
    }
    int size() {
        return root == EMPTY ? 0 : root->size;
    }
} mlist;
struct Pt {
    double x, y;
    Pt() {}
    Pt(int xy[]):Pt(xy[0], xy[1]) {}
    Pt(double x, double y):x(x), y(y) {}
    bool operator<(const Pt &o) const {
        if (x != o.x)	return x < o.x;
        return y < o.y;
    }
};
struct PtP {
    static double x;
    Pt p, q;
    PtP(Pt a, Pt b) {
        p = a, q = b;
        if (q < p)
            swap(p, q);
    }
    double interpolate(const Pt& p1, const Pt& p2, double& x) const {
        if (p1.x == p2.x) return min(p1.y, p2.y);
        return p1.y + (p2.y - p1.y) / (p2.x - p1.x) * (x - p1.x);
    }
    bool operator<(const PtP &o) const {
        return interpolate(p, q, x) < interpolate(o.p, o.q, x);
    }
};
double PtP::x = 1;
struct SegSeg {
    struct Node {
        Node *lson, *rson;
        tree<pair<PtP, int>, null_type, less<pair<PtP, int>>, rb_tree_tag, tree_order_statistics_node_update> segs;
        Node() {
            lson = rson = NULL;
        }
    };
    Node *root;
    int xn;
    Node* newNode() {
        return new Node();
    }
    void freeNode(Node *u) {
        free(u);
    }
    void init() {
        root = NULL;
        xn = mesh.X.size();
    }
    void insert(tuple<int, int, int> e) {
        int p, q, r; tie(p, q, r) = e;
        remove(0, xn-1, {PtP(Pt(mesh.pt[p]), Pt(mesh.pt[r])), r});
        insert(0, xn-1, {PtP(Pt(mesh.pt[p]), Pt(mesh.pt[q])), q});
        insert(0, xn-1, {PtP(Pt(mesh.pt[q]), Pt(mesh.pt[r])), r});
    }
    void remove(tuple<int, int, int> e) {
        int p, q, r; tie(p, q, r) = e;
        remove(0, xn-1, {PtP(Pt(mesh.pt[p]), Pt(mesh.pt[q])), q});
        remove(0, xn-1, {PtP(Pt(mesh.pt[q]), Pt(mesh.pt[r])), r});
        insert(0, xn-1, {PtP(Pt(mesh.pt[p]), Pt(mesh.pt[r])), r});
    }	
    int inside(double x, double y) {
        PtP::x = x;
        return count(root, 0, xn-1, x, y)&1;
    }
    int count(Node* u, int l, int r, double x, double y) {
        if (u == NULL)
            return 0;
        int ret = 0;
        if ((mesh.X[l] > x) != (mesh.X[r] > x))
            ret += u->segs.order_of_key({PtP(Pt(x, y), Pt(x, y)), -1});
        int m = (l+r)/2;
        if (x <= mesh.X[m])
            ret += count(u->lson, l, m, x, y);
        if (x >= mesh.X[m])
            ret += count(u->rson, m, r, x, y);
        return ret;
    }
    void insert(int l, int r, pair<PtP, int> s) {
        if (s.first.p.x != s.first.q.x)
            insert(root, l, r, s);
    }
    void remove(int l, int r, pair<PtP, int> s) {
        if (s.first.p.x != s.first.q.x)
            remove(root, l, r, s);
    }
    void insert(Node* &u, int l, int r, pair<PtP, int> s) {
        if (u == NULL)
            u = newNode();
        if (s.first.p.x <= mesh.X[l] && mesh.X[r] <= s.first.q.x) {
            PtP::x = (mesh.X[l] + mesh.X[r])/2.0;
            u->segs.insert(s);
            return;
        }
        int m = (l+r)/2;
        if (s.first.q.x <= mesh.X[m])			insert(u->lson, l, m, s);
        else if (s.first.p.x >= mesh.X[m])	insert(u->rson, m, r, s);
        else	insert(u->lson, l, m, s), insert(u->rson, m, r, s);
    }
    void remove(Node* u, int l, int r, pair<PtP, int> s) {
        if (u == NULL)
            return;
        if (s.first.p.x <= mesh.X[l] && mesh.X[r] <= s.first.q.x) {
            PtP::x = (mesh.X[l] + mesh.X[r])/2.0;
            u->segs.erase(s);
            return;
        }
        int m = (l+r)/2;
        if (s.first.q.x <= mesh.X[m])			remove(u->lson, l, m, s);
        else if (s.first.p.x >= mesh.X[m])	remove(u->rson, m, r, s);
        else	remove(u->lson, l, m, s), remove(u->rson, m, r, s);
    }
} mbrh;
int main() {
    int n, m, cmd, x, pos;
    double px, py;
    scanf("%d %d", &n, &m);
    mesh.read(n);
    mlist.init(), mbrh.init();
    for (int i = 0; i < m; i++) {
        scanf("%d", &cmd);
        if (cmd == 1) {
            scanf("%d %d", &x, &pos);
            mbrh.insert(mlist.insert(x, pos));
        } else if (cmd == 2) {
            scanf("%d", &x);
            mbrh.remove(mlist.remove(x));
        } else {
            scanf("%lf %lf", &px, &py);
            puts(mbrh.inside(px, py) ? "1" : "0");
        }
    }
    return 0;
}

PBDS + ROPE

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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
#include <bits/stdc++.h>
using namespace std;
#include <ext/rope>
using namespace __gnu_cxx;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
struct Mesh {
static const int MAXN = 1e5 + 5;
    int pt[MAXN][2];
    vector<int> X;
    void read(int n) {
        for (int i = 0; i < n; i++)
            scanf("%d %d", &pt[i][0], &pt[i][1]);
        X.clear(); X.reserve(n);
        for (int i = 0; i < n; i++)
            X.push_back(pt[i][0]);
        sort(X.begin(), X.end());
        X.erase(unique(X.begin(), X.end()), X.end());
    }
} mesh;
class Rope {
public:
    rope<int> r;
    void init() {
        r.clear();
    }
    int next(rope<int>::const_iterator it) {
        it++;
        if (it == r.end())
            return *r.begin();
        return *it;
    }
    int prev(rope<int>::const_iterator it) {
        if (it == r.begin())
            return *r.rbegin();
        it--;
        return *it;
    }
    tuple<int, int, int> insert(int data, int pos) {
        r.insert(pos, data);
        auto it = r.begin() + pos;
        int p = prev(it);
        int q = next(it);
        return make_tuple(p, data, q);
    }
    tuple<int, int, int> remove(int pos) {
        auto it = r.begin() + pos;
        int del = *it;
        int p = prev(it);
        int q = next(it);
        r.erase(pos, 1);
        return make_tuple(p, del, q);
    }
} mlist;
struct Pt {
    double x, y;
    Pt() {}
    Pt(int xy[]):Pt(xy[0], xy[1]) {}
    Pt(double x, double y):x(x), y(y) {}
    bool operator<(const Pt &o) const {
        if (x != o.x)	return x < o.x;
        return y < o.y;
    }
};
struct PtP {
    static double x;
    Pt p, q;
    PtP(Pt a, Pt b) {
        p = a, q = b;
        if (q < p)
            swap(p, q);
    }
    double interpolate(const Pt& p1, const Pt& p2, double& x) const {
        if (p1.x == p2.x) return min(p1.y, p2.y);
        return p1.y + (p2.y - p1.y) / (p2.x - p1.x) * (x - p1.x);
    }
    bool operator<(const PtP &o) const {
        return interpolate(p, q, x) < interpolate(o.p, o.q, x);
    }
};
double PtP::x = 1;
struct SegSeg {
    struct Node {
        Node *lson, *rson;
        tree<pair<PtP, int>, null_type, less<pair<PtP, int>>, rb_tree_tag, tree_order_statistics_node_update> segs;
        Node() {
            lson = rson = NULL;
        }
    };
    Node *root;
    int xn;
    Node* newNode() {
        return new Node();
    }
    void init() {
        root = NULL;
        xn = mesh.X.size();
    }
    void insert(tuple<int, int, int> e) {
        int p, q, r; tie(p, q, r) = e;
        remove(0, xn-1, {PtP(Pt(mesh.pt[p]), Pt(mesh.pt[r])), r});
        insert(0, xn-1, {PtP(Pt(mesh.pt[p]), Pt(mesh.pt[q])), q});
        insert(0, xn-1, {PtP(Pt(mesh.pt[q]), Pt(mesh.pt[r])), r});
    }
    void remove(tuple<int, int, int> e) {
        int p, q, r; tie(p, q, r) = e;
        remove(0, xn-1, {PtP(Pt(mesh.pt[p]), Pt(mesh.pt[q])), q});
        remove(0, xn-1, {PtP(Pt(mesh.pt[q]), Pt(mesh.pt[r])), r});
        insert(0, xn-1, {PtP(Pt(mesh.pt[p]), Pt(mesh.pt[r])), r});
    }	
    int inside(double x, double y) {
        PtP::x = x;
        return count(root, 0, xn-1, x, y)&1;
    }
    int count(Node* u, int l, int r, double x, double y) {
        if (u == NULL)
            return 0;
        int ret = 0;
        if ((mesh.X[l] > x) != (mesh.X[r] > x))
            ret += u->segs.order_of_key({PtP(Pt(x, y), Pt(x, y)), -1});
        if (l == r)
            return ret;
        int m = (l+r)/2;
        if (x <= mesh.X[m])
            ret += count(u->lson, l, m, x, y);
        if (x >= mesh.X[m])
            ret += count(u->rson, m, r, x, y);
        return ret;
    }
    void insert(int l, int r, pair<PtP, int> s) {
        if (s.first.p.x != s.first.q.x)
            insert(root, l, r, s);
    }
    void remove(int l, int r, pair<PtP, int> s) {
        if (s.first.p.x != s.first.q.x)
            remove(root, l, r, s);
    }
    void insert(Node* &u, int l, int r, pair<PtP, int> s) {
        if (u == NULL)
            u = newNode();
        if (s.first.p.x <= mesh.X[l] && mesh.X[r] <= s.first.q.x) {
            PtP::x = (mesh.X[l] + mesh.X[r])/2.0;
            u->segs.insert(s);
            return;
        }
        if (l == r)
            return;
        int m = (l+r)/2;
        if (s.first.q.x <= mesh.X[m])			insert(u->lson, l, m, s);
        else if (s.first.p.x >= mesh.X[m])	insert(u->rson, m, r, s);
        else	insert(u->lson, l, m, s), insert(u->rson, m, r, s);
    }
    void remove(Node* &u, int l, int r, pair<PtP, int> s) {
        if (u == NULL)
            return;
        if (s.first.p.x <= mesh.X[l] && mesh.X[r] <= s.first.q.x) {
            PtP::x = (mesh.X[l] + mesh.X[r])/2.0;
            u->segs.erase(s);
            return;
        }
        if (l == r)
            return;
        int m = (l+r)/2;
        if (s.first.q.x <= mesh.X[m])			remove(u->lson, l, m, s);
        else if (s.first.p.x >= mesh.X[m])	remove(u->rson, m, r, s);
        else	remove(u->lson, l, m, s), remove(u->rson, m, r, s);
    }
} mbrh;
int main() {
    int n, m, cmd, x, pos;
    double px, py;
    scanf("%d %d", &n, &m);
    mesh.read(n);
    mlist.init(), mbrh.init();
    for (int i = 0; i < m; i++) {
        scanf("%d", &cmd);
        if (cmd == 1) {
            scanf("%d %d", &x, &pos);
            mbrh.insert(mlist.insert(x, pos));
        } else if (cmd == 2) {
            scanf("%d", &x);
            mbrh.remove(mlist.remove(x));
        } else {
            scanf("%lf %lf", &px, &py);
            puts(mbrh.inside(px, py) ? "1" : "0");
        }
    }
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

b685. 高中組第五題-課堂抽籤

Problem

$N$ 個人抽籤決定跟誰同一組，請問在某些籤已經決定好的情況下，求恰好分成 $M$ 組的抽籤方法數。

轉換成 $N$ 個節點，恰好形成 $M$ 個環的方法數。

## Sample Input ##

1
2
3
4
5
2
5 1
2 3 1 5 4
5 2
2 3 1 5 4

Sample Output

1
2
0
1

Solution

在此特別感謝 lwc (Wei Chen Liao) 提供思路。

手動暴力打表後，上網蒐到 A125714 Alfred Moessner’s factorial triangle. 恰好是這個數列的答案。

由於每一個人的籤不重複，若把他抽到的籤當作指向出去的邊，那麼保證這一個點恰好一個出邊和一個入邊。當所有籤抽滿後，圖看起來是好幾個環。

遞迴定義 dp[i][j] 表示有 $i$ 個節點和 $j$ 個環。考慮新加入得點要抽到哪一個籤，加入到 $j$ 個環的情況，則是把某一個環的某一個位置打開加入，或者自身形成一個環，最後得到 dp[i][j] = dp[i-1][j-1] + (i-1)*dp[i-1][j]

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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1024;
const long long MOD = 1000007;
long long dp[MAXN][MAXN];
int A[MAXN], used[MAXN];
int main() {
    dp[0][0] = dp[1][1] = 1;
    for (int i = 2; i < MAXN; i++) {
        for (int j = 1; j <= i; j++)
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] * (i-1))%MOD;
    }
    int testcase, n, m;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        int a = n, b = 0;
        memset(used, 0, sizeof(used));
        for (int i = 1; i <= n; i++) {
            if (used[i])
                continue;
            int x = i, cnt = 0;
            while (x && used[x] == 0)
                used[x] = 1, x = A[x], cnt++;
            a -= cnt-1;
            if (x == i)	m--;
            if (x == 0)	b++;
        }
        if (m < 0)
            puts("0");
        else
            printf("%lld\n", dp[b][m]);
    }
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

b500. 子字串集合

Problem

給予一個字串 $S$，求出所有子字串的集合，將集合內除了空字串以外的字串照字典順序輸出。

Sample Input

1
SLEEP

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
E
EE
EEP
EP
L
LE
LEE
LEEP
P
S
SL
SLE
SLEE
SLEEP

Solution

新手上路練習題，沒打算考很難的操作，即便如此信任也破產，看來出成變態題的機會高一點導致釣不到人來寫。

直觀作法是窮舉所有子字串，去掉重複即可，時間複雜度 $O(N^3)$，由於 $N = 500$ 也要考慮輸出的成本，所以不可能出太大。儘管如此，來比較算法之間的空間和時間用量。

首先，最常見到的 set 作法，若直接儲存字串空間用量 $O(N^3)$，為了避免空間太多，可以自己寫一個 compare function 來完成，因此 set 只要記錄子字串的起始位置和長度即可，時間複雜度 $O(N^3)$，空間降到 $O(N^2)$。

接著，進入到後期，常用到字典樹 trie，若把所有後綴插入到字典中，接著在 trie 走訪輸出所有結果即可，時間複雜度 $O(N^2)$，空間 $O(N^2 \times 26)$。可以使用 double-array trie 捨棄掉一點時間，降低節點的空間使用量。

最後，比較強悍的後綴自動機，在劉汝佳的書上主要是用 DAWG (directed acyclic word graph) 來描述 suffix automaton，後綴自動機可以在線構造，時間和空間複雜度都是 $O(N)$，後綴自動機可以接受 $S$ 所有的後綴，關於建造時間和狀態總數的證明可以參考 《Suffix Automaton 杭州外国语学校 陈立杰》 的簡報。

若不想這麼詳細的證明狀態總數和時間複雜度，可以從 AC 自動機的建構概念來思考，一樣有 fail 指針，來維護當一個後綴失去匹配，移除前綴要移動到的狀態。特別的是，每一次增加最多兩個節點，最後一次增加的節點為 accept state (後綴自動機只有一個或兩個 accept state)，其中一個節點是解決當前字串的後綴長度 1 的轉移。

根據這一題的需求，走訪一次後綴自動機就能印出所有子字串。

  • set 解法一 AC (0.2s, 25.2MB)
  • set 解法二 AC (0.4s, 3.8MB)
  • trie AC (0.1s, 12.1MB)
  • Double-array trie AC (0.2s, 7.7MB)
  • 後綴自動機 suffix automaton AC (64ms, 240KB)

後綴自動機

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
#include <bits/stdc++.h>
class SuffixAutomaton {
public:
    static const int MAXN = 500<<1;
    static const int MAXC = 26;
    struct Node {
        Node *next[MAXC], *pre;
        int step;
        Node() {
            pre = NULL, step = 0;
            memset(next, 0, sizeof(next));
        }
    } _mem[MAXN];
    int size;
    Node *root, *tail;	
    void init() {
        size = 0;
        root = tail = newNode();
    }
    Node* newNode() {
        Node *p = &_mem[size++];
        *p = Node();
        return p;
    }
    int toIndex(char c) { return c - 'A'; }
    char toChar(int c) { return c + 'A'; }
    void add(char c, int len) {
        c = toIndex(c);
        Node *p, *q, *np, *nq;
        p = tail, np = newNode();
        np->step = len;
        for (; p && p->next[c] == NULL; p = p->pre)
            p->next[c] = np;
        tail = np;
        if (p == NULL) {
            np->pre = root;
        } else {
            if (p->next[c]->step == p->step+1) {
                np->pre = p->next[c];
            } else {
                q = p->next[c], nq = newNode();
                *nq = *q;
                nq->step = p->step + 1;
                q->pre = np->pre = nq;
                for (; p && p->next[c] == q; p = p->pre)
                    p->next[c] = nq;
            }
        }
    }
    void build(const char *s) {
        init();
        for (int i = 0; s[i]; i++)
            add(s[i], i+1);
    }
    void dfs(Node *u, int idx, char path[]) {
        for (int i = 0; i < MAXC; i++) {
            if (u->next[i]) {
                path[idx] = toChar(i);
                path[idx+1] = '\0';
                puts(path);
                dfs(u->next[i], idx+1, path);
            }
        }
    }
    void print() {
        char s[1024];
        dfs(root, 0, s);
    } 
} SAM;
int main() {
    char s[1024];
    while (scanf("%s", s) == 1) {
        SAM.build(s);
        SAM.print();
    }
    return 0;
}

set ver 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h> 
using namespace std;
int main() {
    char s[512];
    while (scanf("%s", s) == 1) {
        set<string> S;
        int n = strlen(s);
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                char c = s[j+1];
                s[j+1] = '\0';
                S.insert(s+i);
                s[j+1] = c;
            }
        }
        for (auto &x : S)
            puts(x.c_str());
    }
    return 0;
}

set ver 2

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
#include <bits/stdc++.h> 
using namespace std;
char s[512];
struct cmp {
    bool operator() (const pair<int, int> &a, const pair<int, int> &b) const {
        for (int i = 0; i < a.second && i < b.second; i++) {
            if (s[a.first+i] != s[b.first+i])
                return s[a.first+i] < s[b.first+i];
        }
        return a.second < b.second;
    }
};
int main() {
    while (scanf("%s", s) == 1) {
        set< pair<int, int>, cmp > S;
        int n = strlen(s);
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                S.insert({i, j-i+1});
            }
        }
        for (auto &x : S) {
            int base = x.first, len = x.second;
            char c = s[base+len];
            s[base+len] = '\0';
            puts(s + base);
            s[base+len] = c;
        }
    }
    return 0;
}

trie

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
#include <bits/stdc++.h> 
using namespace std;
class Trie {
public:
    static const int MAXN = 130000;
    static const int MAXC = 26;
    struct Node {
        Node *next[MAXC];
        void init() {
            memset(next, 0, sizeof(next));
        }
    } nodes[MAXN];
    Node *root;
    int size;
    Node* newNode() {
    	assert(size < MAXN);
        Node *p = &nodes[size++];
        p->init();
        return p;
    }
    void init() {
        size = 0;
        root = newNode();
    }
    inline int toIndex(char c) {
        return c - 'A';
    }
    inline int toChar(char c) {
        return c + 'A';
    }
    void insert(const char str[]) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = newNode();
            p = p->next[idx];
        }
    }
    void dfs(Node *u, int idx, char path[]) {
        for (int i = 0; i < MAXC; i++) {
            if (u->next[i]) {
                path[idx] = toChar(i);
                path[idx+1] = '\0';
                puts(path);
                dfs(u->next[i], idx+1, path);
            }
        }
    }
    void print() {
        char s[1024];
        dfs(root, 0, s);
    }
} tree;
char s[1024];
int main() {
    while (scanf("%s", s) == 1) {
        int n = strlen(s);
        tree.init();
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                char c = s[j+1];
                s[j+1] = '\0';
                tree.insert(s+i);
                s[j+1] = c;
            }
        }
        tree.print();
    }
    return 0;
}

DA trie

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
#include <bits/stdc++.h> 
using namespace std;
class DATrie {
public:
    static const int MAXN = 500000;
    static const int MAXC = 27;
    struct Node {
        int check, base, fail, val;
    } A[MAXN + MAXC];
    int node_size, mem_size, emp_size;
    //
    int son_pos[MAXC], find_pos;
    inline int toIndex(char c) {
        return c - 'A' + 1;
    }
    inline int toChar(char c) {
        return c + 'A' - 1;
    }
    inline bool isEMPTY(int u) {
    	return u < MAXN && A[u].check < 0 && A[u].base < 0;
    }
    void init() {
        for (int i = 1; i < MAXN; i++)
            A[i].check = -(i+1), A[i].base = -(i-1);
        for (int i = MAXN; i < MAXN + MAXC; i++)
            A[i].check = INT_MAX;
        A[MAXN-1].check = -1, A[1].base = -(MAXN-1);
        A[0].check = -1, A[0].base = 0;
        node_size = mem_size = emp_size = 0, find_pos = 1;
    }
    inline void rm_node(int x) {
        if (find_pos == x)	find_pos = abs(A[x].check);
        A[-A[x].base].check = A[x].check;
        A[-A[x].check].base = A[x].base;
        node_size++;
        mem_size = max(mem_size, x);
    }
    inline void ad_node(int x) {
        A[x].check = MAXN, A[x].base = MAXN;
        emp_size++;
    }
    bool insert(const char *s) {
        int st = 0, to, c;
        int flag = 0;
        for (int i = 0; s[i]; i++) {
            c = toIndex(s[i]);
            to = abs(A[st].base) + c;	
            if (st == abs(A[to].check)) {
                st = to;
            } else if (isEMPTY(to)) {
                rm_node(to); 
                A[to].check = st, A[to].base = to;
                st = to;
            } else {
                int son_sz = 0;
                int pos = find_empty(st, c, son_sz);
                relocate(st, pos, son_sz-1);
                i--; 
            }
        }
        A[st].base = -abs(A[st].base);
        return 1;
    }
    int find(const char *s) {
        int st = 0, to, c;
        for (int i = 0; s[i]; i++) {
            c = toIndex(s[i]);
            to = abs(A[st].base) + c;
            if (st == abs(A[to].check))
                st = to;
            else
                return 0;
        }
        return A[st].base < 0;
    }
    int find_empty(int st, int c, int &sz) {
        sz = 0;
        int bs = abs(A[st].base);
        for (int i = 1, j = bs+1; i < MAXC; i++, j++) {
            if (abs(A[j].check) == st)
                son_pos[sz++] = i;
        }
        son_pos[sz++] = c;
        int mn_pos = min(son_pos[0], c) - 1;
        for (; find_pos && (find_pos < bs || find_pos < mn_pos); find_pos = abs(A[find_pos].check));
        for (; find_pos; find_pos = abs(A[find_pos].check)) {
            int ok = 1;
            for (int i = 0; i < sz && ok; i++)
                ok &= isEMPTY(find_pos + son_pos[i] - mn_pos);
            if (ok)
                return find_pos - mn_pos;
        }
        printf("Memory Leak -- %d\n", find_pos);
        exit(0);
        return -1;
    }
    void relocate(int st, int to, int sz) {	// move ::st -> ::to
        for (int i = sz-1; i >= 0; i--) {
            int a = abs(A[st].base) + son_pos[i];	// old
            int b = to + son_pos[i];			// new
            rm_node(b);
            A[b].check = st, A[b].base = A[a].base;
            int vs = abs(A[a].base);
            for (int j = 1, k = vs+1; j < MAXC; j++, k++) {
                if (abs(A[k].check) == a)
                    A[k].check = b;
            }
            ad_node(a);
        }
        A[st].base = (A[st].base < 0 ? -1 : 1) * to;
    }
    void dfs(int u, int idx, char path[]) {
        for (int i = 1; i < MAXC; i++) {
            int to = abs(A[u].base) + i;
            if (u == abs(A[to].check)) {
                path[idx] = toChar(i);
                path[idx+1] = '\0';
                puts(path);
                dfs(to, idx+1, path);
            }
        }
    }
    void print() {
        char s[1024];
        dfs(0, 0, s);
    }
} tree;
char s[1024];
int main() {
    while (scanf("%s", s) == 1) {
        int n = strlen(s);
        tree.init();
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                char c = s[j+1];
                s[j+1] = '\0';
                tree.insert(s+i);
                s[j+1] = c;
            }
        }
        tree.print();
    }
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

b498. 史蒂芙的單詞統計

Problem

背景

史蒂芙手上有本小字典，這字典專門針對某種類型的需求而收集，字典中有非常多特定單詞，為了要辨識語言是否屬於哪一類，判斷方法就是統計一句話中出現多少次字典的單詞，再按照比例數量去偵測。

題目描述

給予 $N$ 個單詞的字典，每個單詞只由大小寫字母和數字構成，接著有 $Q$ 個詢問，每個詢問為一個字串，字串只由大小寫字母和數字構成。對於每個詢問加總每一種單詞出現在字串的個數。

例如經典遊戲《魂斗羅》的秘笈 UUDDLRLRBA，若字典中只有兩個單詞 LR 和 BA，由於 LR 出現 2 次，BA 出現 1 次，統計結果為 1+2 = 3。同理，BANANANA，若字典中只有 ANA 和 BA，則 ANA 出現 3 次，BA 出現一次，統計結果為 3+1 = 4。

這個工作需要極致的效率，就麻煩各位。由於史蒂芙經費有限，只能給予 128MB 的空間。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
2
01
01
1
01001
3
LR
BA
ANA
2
UUDDLRLRBA
BANANANA

Sample Output

1
2
3
4
5
Case #1:
2
Case #2:
3
4

Solution

史蒂芙系列迎來第七題，這次考驗的是 Trie 和 Aho-Corasick automation 的空間優化，明顯地在 Trie 中每一個節點會帶有 |alpha set| 個 pointer，因此空間使用量非常浪費，尤其後綴的機率極低重疊。

因此，雖然只有大小寫英文和數字的字串，$O(64)$ 空間仍然很大，那麼開平衡樹是個解決方法，但千萬不能使用內建的 std::map，因為實作的 RB tree 帶有的 CONTAINER OVERHEAD 直接佔有大量空間。

  • 解法一： Double-Array Trie + Aho-Corasick automation，DA Trie 原則上在弄 perfect hash，一旦衝突就要捨棄，接著一代子節點跟著搬家，因此宣告一個諾大的內存池，利用雙向鏈表維護，讓他們盡可能找到安居之地。
  • 解法二：原生作法，但使用 vector<Node*> link 來維護，保證 link 的首尾都有實體子節點，中間若發生留空就隨他去，目標省下後綴空間，那後綴運氣好都是在 size = 1 的情況紀錄。
  • 解法三：安妥妥地寫平衡樹。

看到解法二就知道解法一白做工，雖然標榜 DA Trie 在插入能力很低效，修改一下找 perfect hash 的方法，不支持高效率壓縮，多一點垃圾也沒關係，那麼弄成作業系統那樣的檔案配置，看要用 C-LOOK 還是 SCAN 亂幹。總之，每次從頭開始刷會刷到天昏地暗。

  • 解法一：AC (2.5s, 76.8MB)
  • 解法二：AC (2.5s, 53.3MB)
  • 解法三：釣魚中

DA trie

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
179
180
181
#include <bits/stdc++.h> 
using namespace std;
class DATrie {
public:
    static const int MAXN = 5000000;
    static const int MAXC = 63;
    struct Node {
        int check, base, fail, val;
    } A[MAXN + MAXC];
    int node_size, mem_size, emp_size;
    //
    int son_pos[MAXC], find_pos;
    inline int toIndex(char c) {
        if (isdigit(c))	return c - '0' + 1;
        if (isupper(c)) return c - 'A' + 10 + 1;
        if (islower(c))	return c - 'a' + 26 + 10 + 1;
        assert(false);
    }
    inline bool isEMPTY(int u) {
        return u < MAXN && A[u].check < 0 && A[u].base < 0;
    }
    void init() {
        for (int i = 1; i < MAXN; i++)
            A[i].check = -(i+1), A[i].base = -(i-1);
        for (int i = MAXN; i < MAXN + MAXC; i++)
            A[i].check = INT_MAX;
        A[MAXN-1].check = -1, A[1].base = -(MAXN-1);
        A[0].check = -1, A[0].base = 0;
        node_size = mem_size = emp_size = 0, find_pos = 1;
    }
    inline void rm_node(int x) {
        if (find_pos == x)	find_pos = abs(A[x].check);
        A[-A[x].base].check = A[x].check;
        A[-A[x].check].base = A[x].base;
        node_size++;
        mem_size = max(mem_size, x);
    }
    inline void ad_node(int x) {
        A[x].check = MAXN, A[x].base = MAXN;
        emp_size++;
    }
    bool insert(const char *s) {
        int st = 0, to, c;
        int flag = 0;
        for (int i = 0; s[i]; i++) {
            c = toIndex(s[i]);
            to = abs(A[st].base) + c;	
            if (st == abs(A[to].check)) {
                st = to;
            } else if (isEMPTY(to)) {
                rm_node(to); 
                A[to].check = st, A[to].base = to;
                st = to;
            } else {
                int son_sz = 0;
                int pos = find_empty(st, c, son_sz);
                relocate(st, pos, son_sz-1);
                i--; 
            }
        }
//		if (A[st].base > 0)	words++;
        A[st].base = -abs(A[st].base);
        return 1;
    }
    int find(const char *s) {
        int st = 0, to, c;
        for (int i = 0; s[i]; i++) {
            c = toIndex(s[i]);
            to = abs(A[st].base) + c;
            if (st == abs(A[to].check))
                st = to;
            else
                return 0;
        }
        return A[st].base < 0;
    }
    int find_empty(int st, int c, int &sz) {
        sz = 0;
        int bs = abs(A[st].base);
        for (int i = 1, j = bs+1; i < MAXC; i++, j++) {
            if (abs(A[j].check) == st)
                son_pos[sz++] = i;
        }
        son_pos[sz++] = c;
        int mn_pos = min(son_pos[0], c) - 1;
        for (; find_pos && (find_pos < bs || find_pos < mn_pos); find_pos = abs(A[find_pos].check));
        for (; find_pos; find_pos = abs(A[find_pos].check)) {
            int ok = 1;
            for (int i = 0; i < sz && ok; i++)
                ok &= isEMPTY(find_pos + son_pos[i] - mn_pos);
            if (ok)
                return find_pos - mn_pos;
        }
        printf("Memory Leak -- %d\n", find_pos);
        exit(0);
        return -1;
    }
    void relocate(int st, int to, int sz) {	// move ::st -> ::to
        for (int i = sz-1; i >= 0; i--) {
            int a = abs(A[st].base) + son_pos[i];	// old
            int b = to + son_pos[i];			// new
            rm_node(b);
            A[b].check = st, A[b].base = A[a].base;
            int vs = abs(A[a].base);
            for (int j = 1, k = vs+1; j < MAXC; j++, k++) {
                if (abs(A[k].check) == a)
                    A[k].check = b;
            }
            ad_node(a);
        }
        A[st].base = (A[st].base < 0 ? -1 : 1) * to;
    }
    void build() { // AC automation
        queue<int> Q;
        int u, p, to, pto;
        Q.push(0), A[0].fail = -1;
        while (!Q.empty()) {
            u = Q.front(), Q.pop();
            for (int i = 1; i < MAXC; i++) {
                to = abs(A[u].base) + i;
                if (u != abs(A[to].check))	
                    continue;
                Q.push(to);
                p = A[u].fail;
                while (p != -1) {
                    pto = abs(A[p].base) + i;
                    if (p != abs(A[pto].check))
                        p = A[p].fail;
                    else
                        break;
                }
                if (p == -1)
                    A[to].fail = 0;
                else
                    A[to].fail = abs(A[p].base) + i;
                A[to].val = A[A[to].fail].val + (A[to].base < 0);
            }
        }
    }
    int query(const char *s) {
        int st = 0, c, to;
        int matched = 0;
        for (int i = 0; s[i]; i++) {
            c = toIndex(s[i]);
            do {
                to = abs(A[st].base) + c;
                if (st != abs(A[to].check) && st != 0)
                    st = A[st].fail;
                else
                    break;
            } while (true);
            to = abs(A[st].base) + c;
            if (st != abs(A[to].check))
                st = 0;
            else
                st = to;
            matched += A[st].val;
        }
        return matched;
    }
} tree;
char s[1048576];
int main() {
    int n, m, cases = 0;
    while (scanf("%d", &n) == 1) {
        printf("Case #%d:\n", ++cases);
        tree.init();
        for (int i = 0; i < n; i++) {
            scanf("%s", s);
            tree.insert(s);
        }
        tree.build();
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            scanf("%s", s);
            int t = tree.query(s);
            printf("%d\n", t);
        }
    }
    return 0;
}

vector + base

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <map>
#include <assert.h>
#define MAXCHAR 62
#define MAXS (3000005)
#define MAXNODE 1200000
using namespace std;
class ACmachine {
public:
    struct Node {
    	vector<Node*> link;
        Node *fail;
        int cnt, val, base;
        Node() {
            fail = NULL;
            cnt = val = 0;
            base = 128, link = vector<Node*>(0, NULL);
        }
        Node* next(int c) {
        	if (c - base < 0)				return NULL;
        	if (c - base >= link.size())	return NULL;
        	return link[c - base];
        }
        void change(int c, Node *p) {
        	if (c >= base && c - base < link.size()) {
        		link[c-base] = p;
        	} else {
        		int nb = min(base, c), mx = max(base+(int)link.size()-1, c);
        		if (base == 128)	mx = c;
        		vector<Node*> co(mx-nb+1, NULL);
        		for (int i = 0; i < link.size(); i++)
        			co[i+base-nb] = link[i];
        		link = co, base = nb;
        		link[c-base] = p;
            }
        }
    } nodes[MAXNODE];
    Node *root;
    int size;
    Node* getNode() {
    	assert(size < MAXNODE);
        Node *p = &nodes[size++];
        *p = Node();
        return p;
    }
    void init() {
        size = 0;
        root = getNode();
    }
    inline int toIndex(char c) {
        if (isdigit(c))	return c - '0';
        if (isupper(c)) return c - 'A' + 10;
        if (islower(c))	return c - 'a' + 26 + 10;
    }
    void insert(const char str[]) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next(idx) == NULL)
                p->change(idx, getNode());
            p = p->next(idx);
        }
        p->cnt = 1;
    }
    void build() { // AC automation
        queue<Node*> Q;
        Node *u, *p;
        Q.push(root), root->fail = NULL;
        while (!Q.empty()) {
            u = Q.front(), Q.pop();
            for (int i = 0; i < MAXCHAR; i++) {
                if (u->next(i) == NULL)
                    continue;
                Q.push(u->next(i));
                p = u->fail;
                while (p != NULL && p->next(i) == NULL)
                    p = p->fail;
                if (p == NULL)
                    u->next(i)->fail = root;
                else
                    u->next(i)->fail = p->next(i);
                u->next(i)->val = u->next(i)->fail->val + u->next(i)->cnt;
            }
        }
    }
    int query(const char str[]) {
        Node *u = root, *p;
        int matched = 0;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            while (u->next(idx) == NULL && u != root)
                u = u->fail;
            u = u->next(idx);
            u = (u == NULL) ? root : u;
            p = u;
            matched += p->val;
        }
        return matched;
    }
    void free() {
        return ;
    }
};
ACmachine disk;
char s[1048576];
int main() {
    int n, m, cases = 0;
    while (scanf("%d", &n) == 1) {
        printf("Case #%d:\n", ++cases);
        disk.init();
        for (int i = 0; i < n; i++) {
            scanf("%s", s);
            disk.insert(s);
        }
        disk.build();
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            scanf("%s", s);
            int t = disk.query(s);
            printf("%d\n", t);
        }
        disk.free();
    }
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

b494. 史蒂芙的修羅道

Problem

背景

史蒂芙被王國政務工作忙昏頭，每次都要求效率的極限，即使不會玩遊戲，只要把政務工作處理到極致，想必這就是另一種人生價值。

題目描述

回顧一個經典問題區間極大極小值詢問 RMQ，她收到下面這一份代碼

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
#include <bits/stdc++.h>
using namespace std;
unsigned int seed = 0;
unsigned int p_random() {return seed = (seed*9301+49297);}
unsigned int A[5000005];
int main() {
    int N, M, S, x, y;
    unsigned int hash = 0;
    scanf("%d %d %d", &N, &M, &S);
    seed = S;
    for (int i = 1; i <= N; i++)
        A[i] = p_random();
    for (int i = 0; i < M; i++) {
        x = p_random()%N+1, y = p_random()%N+1;
        if (x > y)	swap(x, y);
        unsigned int max_val = A[x];
        for (int j = x; j <= y; j++)
            max_val = max(max_val, A[j]);
        hash ^= max_val; 
    }
    printf("%lu\n", hash);
    return 0;
}

「給定 $N$ 個整數、$M$ 個詢問操作、$S$ 為亂數種子，接著產生 $N$ 個數字，對於接下來 $M$ 個詢問，每一個詢問兩個整數，輸出區間內的最大值。」這對曾經的史蒂芙而言，用過 Segment Tree、Sparse Table、Unrolled Linked List 解決過，時間、空間複雜度都非常優秀。

現在的工作就是加速這一份代碼。

Sample Input

1
8 5 10

Sample Output

1
4049919279

Solution

經典 RMQ 問題，主要有以下四種，最後一種只支持離線不帶修改的操作。

  • sqrt-decomposition $O(N)$ - $O(\sqrt{N})$
  • sparse table $O(N \log N)$ - $O(1)$
  • segment tree $O(N)$ - $O(\log N)$
  • cartesian tree + tarjan LCA algorithm + morris traversal $O(N + Q)$

於是出了這一題 b494. 史蒂芙的修羅道，把第一種算法卡時間、第二種算法卡空間、第三種算法卡常數。

實作起來非常變態，速度一不小心就會輸非遞迴的 segment tree (zkw 線段樹或者稱做 non-recursive segment tree 的實作技巧，詳見 codeforce - Efficient and easy segment trees )，儘管如此還是卡不住這類的實作，但時間上把遞迴實作的版本卡 TLE，速度略贏 prefect tree 的 segment tree 的實作，但使用空間多了兩倍。

  • 不開 std::vector，否則記憶體會預保留一倍。
  • 使用 tarjan LCA algorithm 在笛卡爾樹二元樹上時要特化操作。
  • 無法使用遞迴，實作非遞迴的二元搜尋樹走訪常數要注意。

通常 tarjan LCA algorithm 會把一個詢問拆成兩個詢問，常數會多 1。在笛卡爾樹上有一個性質，每一個節點的狀態為 <key, value> 看 key 仍然是一個二元搜尋樹，看 value 是一個 heap，在完成 tarjan LCA algorithm 需要的是後序走訪，能保證回答 LCA(x, y) 的順序。假設詢問 LCA(x, y) && x < y 只需要在 y 節點準備詢問 x 即可。

若要降空間複雜度常數，利用 morris traversal 在空間複雜度 $O(1)$ 完成。若使用 stack<> 模擬 tarjan LCA algorithm，最慘的空間複雜度是 $O(N)$。

morris traversal

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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5000005, MAXQ = 5000005;
struct Node {
    int idx;
    Node *ch[2], *fa;
    Node() {
        idx = 0;
        ch[0] = ch[1] = fa = NULL;
    }
} nodes[MAXN];
struct QEdge {
    int u;
    QEdge *next;
};
QEdge qedge[MAXQ], *qadj[MAXN] = {};
unsigned int A[MAXN], eq, ret;
int parent[MAXN];
void init(int n) {
    eq = 0;
    for (int i = 0; i <= n; i++)
        parent[i] = i /*, qadj[i] = NULL */;
}
void insert(Node *u, Node *p) {
    while (A[p->idx] < A[u->idx])	p = p->fa;
    u->ch[0] = p->ch[1];
    if (p->ch[1])	p->ch[1]->fa = u;
    p->ch[1] = u;
    u->fa = p;
}
void build(int N) {
    nodes[0] = Node(), A[0] = UINT_MAX;
    for (int i = 1; i <= N; i++) {
        nodes[i] = Node(), nodes[i].idx = i;
        insert(&nodes[i], &nodes[i-1]);
    }
}
int findp(int x) {
    return parent[x] == x ? x : parent[x]=findp(parent[x]);
}
void tree_reverse(Node *from, Node *to) {
    if (from == to)	return ;
    Node *x = from, *y = from->ch[1], *z;
    while (true) {
        z = y->ch[1];
        y->ch[1] = x;
        x = y, y = z;
        if (x == to)
            return ;
    }
}
void print_reverse(Node *from, Node *to) {
    tree_reverse(from, to);
    Node *p = to;
    while (true) {
        int u = p->idx;
        for (QEdge *e = qadj[u]; e; e = e->next)
            ret ^= A[findp(e->u)];
        if (p->fa != NULL)	parent[findp(u)] = p->fa->idx;
        if (p == from)	break;
        p = p->ch[1];
    }		
    tree_reverse(to, from);
}
void tarjan(Node *root) {	
    Node *cur, *prev, tmp;
    tmp.ch[0] = root;
    cur = &tmp, prev = NULL;
    while (cur != NULL) {
        if (cur->ch[0] == NULL) {
            cur = cur->ch[1];
        } else {
            prev = cur->ch[0];
            while (prev->ch[1] != NULL && prev->ch[1] != cur)
                prev = prev->ch[1];
            if (prev->ch[1] == NULL) {
                prev->ch[1] = cur, cur = cur->ch[0];
            } else {
                print_reverse(cur->ch[0], prev);
                prev->ch[1] = NULL, cur = cur->ch[1];
            }
        }
    }
}
void add(int x, int y, int qid) {
    if (x < y)	swap(x, y);
    qedge[eq].u = y, qedge[eq].next = qadj[x], qadj[x] = &qedge[eq++];
}
unsigned int seed = 0;
unsigned int gen() {return seed = (seed*9301+49297);}
int N, M, S, x, y;
int main() {
    scanf("%d %d %d", &N, &M, &S);
    seed = S, init(N);
    for (int i = 1; i <= N; i++)
        x = gen(), A[i] = x;
    for (int i = 0; i < M; i++) {
        x = gen()%N+1, y = gen()%N+1;
        add(x, y, i);
    }
    ret = 0;
    build(N), tarjan(nodes[0].ch[1]);
    printf("%lu\n", ret);
    return 0;
}

stack

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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5000005, MAXQ = 5000005;
struct Node {
    int idx;
    Node *ch[2], *fa;
    Node() {
        idx = 0;
        ch[0] = ch[1] = fa = NULL;
    }
} nodes[MAXN];
struct QEdge {
    int u;
    QEdge *next;
};
QEdge qedge[MAXQ], *qadj[MAXN] = {};
unsigned int A[MAXN], eq, ret;
int parent[MAXN];
void init(int n) {
    eq = 0;
    for (int i = 0; i <= n; i++)
        parent[i] = i /*, qadj[i] = NULL */;
}
void insert(Node *u, Node *p) {
    while (A[p->idx] < A[u->idx])	p = p->fa;
    u->ch[0] = p->ch[1];
    if (p->ch[1])	p->ch[1]->fa = u;
    p->ch[1] = u;
    u->fa = p;
}
void build(int N) {
    nodes[0] = Node(), A[0] = UINT_MAX;
    for (int i = 1; i <= N; i++) {
        nodes[i] = Node(), nodes[i].idx = i;
        insert(&nodes[i], &nodes[i-1]);
    }
}
int findp(int x) {
    return parent[x] == x ? x : parent[x]=findp(parent[x]);
}
pair<Node*, int> stk[MAXN];
void tarjan(Node *root) {
    int top = -1, u;
    Node *p;
    stk[++top] = {root, 0};
    while (top >= 0) {
        pair<Node*, int> &x = stk[top];
        x.second++;
        if (x.second == 1) {
            if (x.first->ch[0])
                stk[++top] = {x.first->ch[0], 0};
        } else if (x.second == 2) {
            if (x.first->ch[1])
                stk[++top] = {x.first->ch[1], 0};
        } else {
            top--;
            p = x.first, u = p->idx;
            for (QEdge *e = qadj[u]; e; e = e->next)
                ret ^= A[findp(e->u)];
            parent[findp(u)] = p->fa->idx;
        }
    }
}
void add(int x, int y, int qid) {
    if (x < y)	swap(x, y);
    qedge[eq].u = y, qedge[eq].next = qadj[x], qadj[x] = &qedge[eq++];
}
unsigned int seed = 0;
unsigned int gen() {return seed = (seed*9301+49297);}
int N, M, S, x, y;
int main() {
    scanf("%d %d %d", &N, &M, &S);
    seed = S, init(N);
    for (int i = 1; i <= N; i++)
        A[i] = gen();
    for (int i = 0; i < M; i++) {
        x = gen()%N+1, y = gen()%N+1;
        add(x, y, i);
    }
    ret = 0;
    build(N), tarjan(nodes[0].ch[1]);
    printf("%lu\n", ret);
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

b493. 史蒂芙的外交夥伴

Problem

背景

史蒂芙終於有了夥伴，夥伴們各自為了人類國家出訪外交，在大陸版圖中有 $N$ 個小城市，每個城市都有各自的文明發展程度 $A_i$，史蒂芙的夥伴擁有各自能力 $K$ 只能選擇文明發展程度 $A_i$ 小於等於 $K$ 的國家拜訪。一開始國家跟國家之間彼此不相連，隨著外交拓展，小城市決定為史蒂芙的人類國家開一條道路通行另一個小城市，但如果這兩個小城市可以藉由直接相連或間接相連，那這一條道路將不會被建造。

礙於時間有限，史蒂芙手頭上有數個計劃，打算對起點城市到終點城市策劃行程，現在請你算出所有計畫的走訪個數。

題目描述

給定 $N$ 個城市版圖以及 $Q$ 個詢問，一開始城市彼此都不相連，詢問操作有以下兩種

  • 0 X Y 建造城市編號 X 到城市編號 Y 的雙向道路。如果 X 和 Y 本身已經直接相連或間接相連，則忽略此操作。
  • 1 X Y K 詢問路線 X 到 Y 的行程規劃，當夥伴的能力為 $K$ 能走訪的國家個數。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
7 11
1 5 2 6 3 7 4
0 2 4
0 1 2
0 1 3
0 3 7
1 4 7 3
1 7 4 5
0 2 5
0 5 3
1 1 4 5
0 1 4
1 7 4 6

Sample Output

1
2
3
4
2
0
2
3

Solution

在樹上套用函數式線段樹，維護有根樹和 LCA 的操作，將父節點的線段樹狀態傳遞給子節點進行持久化的變動，詢問 x 到 y 路徑時利用區間加減法，計算 x, y, LCA(x, y) 到根的符合條件的數量，統計一下即可。

由於一開始不是完整的一棵樹，會逐漸合成一棵樹，利用啟發式合併，也就是最傳統的合併操作，將小的集合合併到大的集合，合併複雜度為小集合的大小，那複雜度保證 $O(N \log N)$。

在套用函數式線段樹後，合併操作必須在 $O(N \log N)$ 時間完成，空間複雜度也是 $O(N \log N)$，因此完全所有合併操作需要 $O(N \log^2 N)$ 的時間，空間複雜度仍然是 $O(N \log N)$，若沒有搭配垃圾回收，空間會變成 $O(N \log^2 N)$ 的需求。

關於垃圾回收，建議使用 std::queue<> 完成，因為佔有空間少空間常數是 2，若使用 std::vector<> 空間常數是 2，但多餘的部分保證不會用到，就變得相當浪費。一旦支持垃圾回收，空間使用會逐漸變得不連續性，碎片化會造成 cache 的能力降低。速度上會慢上許多。若預先支付空間或者直接浪費 $O(N \log^2 N)$ 的空間都是可以被接受的方案。

在 LCA 計算，需要 $O(N \log N)$ 的時間建表以及 $O(N \log N)$ 的空間，詢問複雜度是 $O(\log N)$。若要降空間複雜度為 $O(N)$，可以用 Link/Cut Tree 代替，由於 splay tree 實作關係，時間複雜度常數略個三四倍。

垃圾回收

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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#include <bits/stdc++.h> 
using namespace std;
class SegementTree {
public:
    static const int MAXN = 1000000;
    static const int MAXV = 50005;
    struct Node {
        Node *lson, *rson;
        int sum;
        Node() {
        	lson = rson = NULL;
        	sum = 0;
        }
    } _mem[MAXN];
    int L, R, V, mem_buf, mem_idx;
    queue<Node*> mem_bin[MAXV], bin;
    inline void clear_bin(int x) {
        while (!mem_bin[x].empty()) {
            recycle(mem_bin[x].front());
            mem_bin[x].pop();
        }
    }
    inline void recycle(Node *x) {
        bin.push(x);
    }
    Node* init(int l, int r, int v) {
        L = l, R = r, V = v;
        mem_buf = 0;
        for (int i = 0; i <= v; i++) {
            while (!mem_bin[i].empty())	mem_bin[i].pop();
        }
        while (!bin.empty())	bin.pop();
        Node* root = build(l, r);
        return root;
    }
    Node* newNode() {
        Node *u;
        if (mem_buf < MAXN) {
            u = &_mem[mem_buf++];
        } else {
            assert(!bin.empty());
            u = bin.front(), bin.pop();
        }
        *u = Node();
        mem_bin[mem_idx].push(u);
        return u;
    }
    Node* cloneNode(Node *p) {
        Node* u = newNode();
        *u = *p;
        return u;
    }
    Node* build(int l, int r) {
        if (l > r)  return NULL;
        Node *u = newNode();
        if (l == r) {
        } else {
            int m = (l + r)/2;
        	u->lson = build(l, m);
        	u->rson = build(m+1, r);
        }
        return u;
    }
    Node* change(Node *p, int x, int l, int r) {
        assert(p != NULL);
        Node *u = cloneNode(p);
        u->sum++;
        if (l == r) {
        } else {
        	int mid = (l + r)/2;
        	if (x <= mid)
            	u->lson = change(p->lson, x, l, mid);
        	else
         		u->rson = change(p->rson, x, mid+1, r);
        }
        return u;
    }
    Node* change(Node *p, int x) {
        return change(p, x, L, R);
    }
    
    int QD;
    void find(Node *v1, int x, int l, int r) {
        if (1 <= l && r <= x) {
        	QD += v1->sum;
        	return ;
        }
        int mid = (l + r)/2;
        if (x <= mid) {
            find(v1->lson, x, l, mid);
        } else {
            find(v1->lson, x, l, mid);
            find(v1->rson, x, mid+1, r);
        }
    }
    int find(Node *v1, int x) {
        QD = 0;
        find(v1, x, L, R);
        return QD;
    }
} tree;
const int MAXN = 65536;
const int MAXLOGN = 17;
SegementTree::Node *root[MAXN];
int A[MAXN];
int fa[MAXLOGN][MAXN], dep[MAXN];
int parent[MAXN], weight[MAXN];
vector<int> g[MAXN];
void dfs(int u, int p, vector<int> &vA) {
    root[u] = tree.change(root[p], A[u]);
    fa[0][u] = p, dep[u] = dep[p] + 1;
    vA.push_back(u);
    for (auto v : g[u]) {
        if (v == p)	continue;
        dfs(v, u, vA);
    }
}
int findp(int x) {
    return x == parent[x] ? x : (parent[x]=findp(parent[x]));
}
int LCA(int x, int y) {
    if (dep[x] < dep[y])	swap(x, y);
    int d = dep[x] - dep[y];
    for (int i = MAXLOGN-1; i >= 0; i--) {
        if ((d>>i)&1) {
            d -= 1<<i;
            x = fa[i][x];
        }
    }
    if (x == y)	return x;
    for (int i = MAXLOGN-1; i >= 0; i--) {
        if (fa[i][x] != fa[i][y]) {
            x = fa[i][x], y = fa[i][y];
        }
    }
    return fa[0][x];
}
void merge(int X, int Y) {
    if (findp(X) == findp(Y))	return ;
    int rx, ry;
    rx = findp(X), ry = findp(Y);
    if (weight[rx] < weight[ry])	swap(rx, ry), swap(X, Y);
    g[X].push_back(Y), g[Y].push_back(X);
    // merge Y's group into X's group
    tree.clear_bin(ry), tree.mem_idx = rx;
    vector<int> vA;
    dfs(Y, X, vA);
    for (int i = 1; i < MAXLOGN; i++) {
        for (auto j : vA)
            fa[i][j] = fa[i-1][fa[i-1][j]];
    }	
    parent[ry] = rx, weight[rx] += weight[ry];
}
int path(int X, int Y, int K) {
    if (findp(X) != findp(Y))	return 0;
    int rx, ry, lca;
    rx = findp(X), ry = findp(Y);
    lca = LCA(X, Y);
    int ret = tree.find(root[X], K) + tree.find(root[Y], K) - tree.find(root[lca], K) * 2;
    ret += A[lca] <= K;
    return ret;
}
int main() {
    int N, Q, cmd;
    int X, Y, K;
    while (scanf("%d %d", &N, &Q) == 2) {
        for (int i = 1; i <= N; i++)
            scanf("%d", &A[i]);
            
        for (int i = 1; i <= N; i++)
            parent[i] = i, weight[i] = 1, g[i].clear(), dep[i] = 0;
        for (int i = 0; i < MAXLOGN; i++)
            for (int j = 0; j <= N; j++)
                fa[i][j] = 0;
            
        tree.mem_idx = 0;
        root[0] = tree.init(1, N, N);
        for (int i = 1; i <= N; i++)
            root[i] = root[0];
        
        int d = 0;
        for (int i = 0; i < Q; i++) {
            scanf("%d %d %d", &cmd, &X, &Y);
            X ^= d, Y ^= d;
            if (cmd == 0) {
                merge(X, Y);
            } else {
                scanf("%d", &K), K ^= d;
                d = path(X, Y, K);
                printf("%d\n", d);
            }
        }
    }
    return 0;
}

預先支付空間

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
179
#include <bits/stdc++.h> 
using namespace std;
int log2int(int x){
    return __builtin_clz((int)1)-__builtin_clz(x);
}
class SegementTree {
public:
    static const int MAXN = 1000000;
    static const int MAXV = 50005;
    struct Node {
        Node *lson, *rson;
        int sum;
        Node() {
        	lson = rson = NULL;
        	sum = 0;
        }
    } _mem[MAXN];
    int L, R, V, mem_idx;
    Node* init(int l, int r, int v) {
        L = l, R = r, V = v;
        mem_idx = 0;
        Node* root = build(l, r);
        return root;
    }
    inline Node* newNode() {
        Node *u = &_mem[mem_idx++];
        *u = Node();
        return u;
    }
//	inline Node* cloneNode(Node *p) {
//		Node *u = &_mem[mem_idx++];
//		*u = *p;
//		return u;
//	}
    Node* build(int l, int r) {
        if (l > r)  return NULL;
        Node *u = newNode();
        if (l == r) {
        } else {
            int m = (l + r)/2;
        	u->lson = build(l, m);
        	u->rson = build(m+1, r);
        }
        return u;
    }
    Node* change(Node *p, Node **sp, int x, int l, int r) {
//		Node *u = cloneNode(p);
        Node *u = *sp;
        *u = *p;
        u->sum++;
        if (l == r) {
        } else {
        	int mid = (l + r)/2;
        	if (x <= mid)
            	u->lson = change(p->lson, sp+1, x, l, mid);
        	else
         		u->rson = change(p->rson, sp+1, x, mid+1, r);
        }
        return u;
    }
    Node* change(Node *p, Node **sp, int x) {
        return change(p, sp, x, L, R);
    }
    
    int QD;
    void find(Node *v1, int x, int l, int r) {
        if (1 <= l && r <= x) {
        	QD += v1->sum;
        	return ;
        }
        int mid = (l + r)/2;
        if (x <= mid) {
            find(v1->lson, x, l, mid);
        } else {
            find(v1->lson, x, l, mid);
            find(v1->rson, x, mid+1, r);
        }
    }
    int find(Node *v1, int x) {
        QD = 0;
        find(v1, x, L, R);
        return QD;
    }
} tree;
const int MAXN = 50005;
const int MAXLOGN = 17;
SegementTree::Node *root[MAXN], *pre_mem[MAXN][MAXLOGN];
int A[MAXN];
int fa[MAXN][MAXLOGN], dep[MAXN];
int parent[MAXN], weight[MAXN];
vector<int> g[MAXN];
void dfs(int u, int p, vector<int> &vA) {
    root[u] = tree.change(root[p], pre_mem[u], A[u]);
    fa[u][0] = p, dep[u] = dep[p] + 1;
    vA.push_back(u);
    for (auto v : g[u]) {
        if (v == p)	continue;
        dfs(v, u, vA);
    }
}
int findp(int x) {
    return x == parent[x] ? x : (parent[x]=findp(parent[x]));
}
int LCA(int x, int y) {
    if (dep[x] < dep[y])	swap(x, y);
    int d = dep[x] - dep[y];
    int LOGN = log2int(dep[x]);
    for (int i = LOGN; i >= 0; i--) {
        if ((d>>i)&1)
            d -= 1<<i, x = fa[x][i];
    }
    if (x == y)	return x;
    for (int i = LOGN; i >= 0; i--) {
        if (fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    }
    return fa[x][0];
}
void merge(int X, int Y) {
    if (findp(X) == findp(Y))	return ;
    int rx, ry;
    rx = findp(X), ry = findp(Y);
    if (weight[rx] > weight[ry])	swap(rx, ry), swap(X, Y);
    g[X].push_back(Y), g[Y].push_back(X);
    // merge Y's group into X's group
    parent[rx] = ry, weight[ry] += weight[rx];
    vector<int> vA;
    dfs(X, Y, vA);
    int LOGN = log2int(weight[ry]);
    for (int i = 1; i <= LOGN; i++) {
        for (auto j : vA)
            fa[j][i] = fa[fa[j][i-1]][i-1];
    }	
}
int path(int X, int Y, int K) {
    if (findp(X) != findp(Y))	return 0;
    int lca = LCA(X, Y);
    int ret = tree.find(root[X], K) + tree.find(root[Y], K) - tree.find(root[lca], K) * 2;
    ret += A[lca] <= K;
    return ret;
}
int main() {
    int N, Q, cmd;
    int X, Y, K;
    while (scanf("%d %d", &N, &Q) == 2) {
        for (int i = 1; i <= N; i++)
            scanf("%d", &A[i]);
            
        for (int i = 1; i <= N; i++)
            parent[i] = i, weight[i] = 1, g[i].clear(), dep[i] = 0;
        for (int i = 0; i < MAXLOGN; i++)
            for (int j = 0; j <= N; j++)
                fa[j][i] = 0;
            
        root[0] = tree.init(1, N, N);
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < MAXLOGN; j++)
                pre_mem[i][j] = tree.newNode();
            root[i] = tree.change(root[0], pre_mem[i], A[i]);
        }
        
        int d = 0;
        for (int i = 0; i < Q; i++) {
            scanf("%d %d %d", &cmd, &X, &Y);
            X ^= d, Y ^= d;
            if (cmd == 0) {
                merge(X, Y);
            } else {
                scanf("%d", &K);
                K ^= d;
                d = path(X, Y, K);
                printf("%d\n", d);
            }
        }
    }
    return 0;
}

內存用盡

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
#include <bits/stdc++.h> 
using namespace std;
int log2int(int x) {
    return __builtin_clz((int)1)-__builtin_clz(x);
}
class SegementTree {
public:
    static const int MAXN = 7000000;
    static const int MAXV = 50005;
    struct Node {
        Node *lson, *rson;
        int sum;
        Node() {
        	lson = rson = NULL;
        	sum = 0;
        }
    } _mem[MAXN];
    int L, R, V, mem_idx;
    Node* init(int l, int r, int v) {
        L = l, R = r, V = v;
        mem_idx = 0;
        Node* root = build(l, r);
        return root;
    }
    inline Node* newNode() {
        Node *u = &_mem[mem_idx++];
        *u = Node();
        return u;
    }
    inline Node* cloneNode(Node *p) {
        Node *u = &_mem[mem_idx++];
        *u = *p;
        return u;
    }
    Node* build(int l, int r) {
        if (l > r)  return NULL;
        Node *u = newNode();
        if (l == r) {
        } else {
            int m = (l + r)/2;
        	u->lson = build(l, m);
        	u->rson = build(m+1, r);
        }
        return u;
    }
    Node* change(Node *p, int x, int l, int r) {
        Node *u = cloneNode(p);
        u->sum++;
        if (l == r) {
        } else {
        	int mid = (l + r)/2;
        	if (x <= mid)
            	u->lson = change(p->lson, x, l, mid);
        	else
         		u->rson = change(p->rson, x, mid+1, r);
        }
        return u;
    }
    Node* change(Node *p, int x) {
        return change(p, x, L, R);
    }
    
    int QD;
    void find(Node *v1, int x, int l, int r) {
        if (1 <= l && r <= x) {
        	QD += v1->sum;
        	return ;
        }
        int mid = (l + r)/2;
        if (x <= mid) {
            find(v1->lson, x, l, mid);
        } else {
            find(v1->lson, x, l, mid);
            find(v1->rson, x, mid+1, r);
        }
    }
    int find(Node *v1, int x) {
        QD = 0;
        find(v1, x, L, R);
        return QD;
    }
} tree;
const int MAXN = 50005;
const int MAXLOGN = 16;
SegementTree::Node *root[MAXN];
int A[MAXN];
int fa[MAXLOGN][MAXN], dep[MAXN];
int parent[MAXN], weight[MAXN];
vector<int> g[MAXN];
void dfs(int u, int p, vector<int> &vA) {
    root[u] = tree.change(root[p], A[u]);
    fa[0][u] = p, dep[u] = dep[p] + 1;
    vA.push_back(u);
    for (auto v : g[u]) {
        if (v == p)	continue;
        dfs(v, u, vA);
    }
}
int findp(int x) {
    return x == parent[x] ? x : (parent[x]=findp(parent[x]));
}
int LCA(int x, int y) {
    if (dep[x] < dep[y])	swap(x, y);
    int d = dep[x] - dep[y];
    int LOGN = log2int(dep[x]);
    for (int i = LOGN; i >= 0; i--) {
        if ((d>>i)&1)
            d -= 1<<i, x = fa[i][x];
    }
    if (x == y)	return x;
    for (int i = LOGN; i >= 0; i--) {
        if (fa[i][x] != fa[i][y])
            x = fa[i][x], y = fa[i][y];
    }
    return fa[0][x];
}
void merge(int X, int Y) {
    if (findp(X) == findp(Y))	return ;
    int rx, ry;
    rx = findp(X), ry = findp(Y);
    if (weight[rx] < weight[ry])	swap(rx, ry), swap(X, Y);
    g[X].push_back(Y), g[Y].push_back(X);
    // merge Y's group into X's group
    parent[ry] = rx, weight[rx] += weight[ry];
    vector<int> vA;
    dfs(Y, X, vA);
    int LOGN = log2int(weight[rx]);
    for (int i = 1; i <= LOGN; i++) {
        for (auto j : vA)
            fa[i][j] = fa[i-1][fa[i-1][j]];
    }	
}
int path(int X, int Y, int K) {
    if (findp(X) != findp(Y))	return 0;
    int lca = LCA(X, Y);
    int ret = tree.find(root[X], K) + tree.find(root[Y], K) - tree.find(root[lca], K) * 2;
    ret += A[lca] <= K;
    return ret;
}
int main() {
    int N, Q, cmd;
    int X, Y, K;
    while (scanf("%d %d", &N, &Q) == 2) {
        for (int i = 1; i <= N; i++)
            scanf("%d", &A[i]);
            
        for (int i = 1; i <= N; i++)
            parent[i] = i, weight[i] = 1, g[i].clear(), dep[i] = 0;
        for (int i = 0; i < MAXLOGN; i++)
            for (int j = 0; j <= N; j++)
                fa[i][j] = 0;
            
        root[0] = tree.init(1, N, N);
        for (int i = 1; i <= N; i++)
            root[i] = root[0];
        
        int d = 0;
        for (int i = 0; i < Q; i++) {
            scanf("%d %d %d", &cmd, &X, &Y);
            X ^= d, Y ^= d;
            if (cmd == 0) {
                merge(X, Y);
            } else {
                scanf("%d", &K);
                K ^= d;
                d = path(X, Y, K);
                printf("%d\n", d);
            }
        }
    }
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

b492. 史蒂芙的外交序列

Problem

背景

史蒂芙為了人類國家決定出遠門外交，在一條神秘谷徑中有 $N$ 個小城市，每個城市都有各自的文明發展程度 $A_i$，史蒂芙依照自己的能力 $K$ 只能選擇文明發展程度 $A_i$ 小於等於 $K$ 的國家拜訪，並且這次遠門的滿意程度是所有走訪國家的權重相乘。

礙於時間有限，史蒂芙手頭上有數個計劃，打算對某個區間內的城市策劃行程，現在請你算出所有計畫的預期滿意程度以及走訪個數，由於滿意程度會很大，輸出 $\mod 1000000007$ 的結果。

題目描述

給定 $N$ 個整數序列 $A[]$ 以及 $Q$ 個詢問，每一個詢問 $[L, R]$ 以及 $K$，請計算 $\sum_{L \le i \le R } [A_i \le K]$ 以及 $\prod_{L \le i \le R, \; A_i \le K } A_i$

Sample Input

1
2
3
4
5
6
7 4
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
4 6 6

Sample Output

1
2
3
4
2 6
0 0
3 6
2 18

Solution

詢問一個區間內，元素小於等於 $K$ 的元素個數，並且把這些數字相乘輸出。

這裡使用函數式線段樹來完成操作，時間複雜度 $O(Q \log N)$ 空間複雜度 $O(N \log N)$。但若模數不是大質數，相乘結果無法利用區間加減法的性質計算，要使用別的資料結構完成，函數式線段樹將沒辦法支持這個計算。

特別小心實作反元素計算時，要分開計算比較好，儘管歐基里德輾轉相除法複雜度 $O(\log N)$ 且常數非常小，詢問時避免兩個版本好同時計算，寫法如下

1
2
3
4
5
6
7
void find(Node *v1, Node *v2, int x, int l, int r) {
    if (1 <= l && r <= x) {
    	QV = QV * v1->prod %MOD * inverse(v2->prod, MOD) % MOD;
    	QD += v1->sum - v2->sum;
    	return ;
    }
...

單筆詢問時間複雜度會掉回 $O(\log^2 N)$。

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
#include <bits/stdc++.h> 
using namespace std;
const int MOD = 1000000007;
void exgcd(int x, int y, int &g, int &a, int &b) {
    if (y == 0)
        g = x, a = 1, b = 0;
    else
        exgcd(y, x%y, g, b, a), b -= (x/y) * a;
}
int inverse(int x, int p) {
    int g, b, r;
    exgcd(x, p, g, r, b);
    if (g < 0)	r = -r;
    return (r%p + p)%p;
}
class SegementTree {
public:
    static const int MAXN = 1000000;
    struct Node {
        Node *lson, *rson;
        int sum, prod;
        Node() {
        	lson = rson = NULL;
        	prod = 1, sum = 0;
        }
    } nodes[MAXN];
    int nodesize, L, R;
    Node* init(int l, int r) {
        nodesize = 0;
        L = l, R = r;
        Node* root = build(l, r);
        return root;
    }
    Node* newNode() {
        Node *u = &nodes[nodesize++];
        *u = Node();
        return u;
    }
    Node* cloneNode(Node *p) {
        Node* u = &nodes[nodesize++];
        *u = *p;
        return u;
    }
    Node* build(int l, int r) {
        if (l > r)  return NULL;
        Node *u = newNode();
        if (l == r) {
        } else {
            int m = (l + r)/2;
        	u->lson = build(l, m);
        	u->rson = build(m+1, r);
        }
        return u;
    }
    Node* change(Node *p, int x, long long val, int l, int r) {
        Node *u = cloneNode(p);
        u->prod = (u->prod * val)%MOD, u->sum++;
        if (l == r) {
        } else {
        	int mid = (l + r)/2;
        	if (x <= mid)
            	u->lson = change(p->lson, x, val, l, mid);
        	else
         		u->rson = change(p->rson, x, val, mid+1, r);
        }
        return u;
    }
    Node* change(Node *p, int x, long long val) {
        return change(p, x, val, L, R);
    }
    
    int QV, QD;
    void find(Node *v1, int x, int l, int r) {
        if (1 <= l && r <= x) {
        	QV = (long long)QV * v1->prod % MOD;
        	QD += v1->sum;
        	return ;
        }
        int mid = (l + r)/2;
        if (x <= mid) {
            find(v1->lson, x, l, mid);
        } else {
            find(v1->lson, x, l, mid);
            find(v1->rson, x, mid+1, r);
        }
    }
    pair<int, int> find(Node *v1, int x) {
        QV = 1, QD = 0;
        find(v1, x, L, R);
        return {QD, QV};
    }
} tree;
const int MAXN = 65536;
SegementTree::Node *root[MAXN];
int main() {
    int N, Q, A[MAXN];
    int L, R, K;
    while (scanf("%d %d", &N, &Q) == 2) {
        for (int i = 1; i <= N; i++)
            scanf("%d", &A[i]);
            
        root[0] = tree.init(1, N);
        for (int i = 1; i <= N; i++)
            root[i] = tree.change(root[i-1], A[i], A[i]);
        
        for (int i = 0; i < Q; i++) {
            scanf("%d %d %d", &L, &R, &K);
            int a, b;
            pair<int, int> r;
            r = tree.find(root[R], K);
            a = r.first, b = r.second;
            r = tree.find(root[L-1], K);
            a -= r.first, b = (long long) b * inverse(r.second, MOD)%MOD;
            if (a == 0) {
                printf("0 0\n");
            } else {
                printf("%d %d\n", a, b);
            }
        }
    }
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

b491. 史蒂芙的政務工作

Problem

背景

史蒂芙接管人類最後國家的政務工作，卻時常受到熊孩子搗亂，文書資料原本按照編號 $[1 \cdots N]$ 排成一疊，熊孩子每一次搗亂都會翻轉位置 $[L, R]$ 的資料，使得編號整個反過來。

史蒂芙已經無暇處理這些熊孩子，她只想知道某個資料現在到底在哪個位置上。

題目描述

給定 $N$ 個整數 $1 \cdots N$ 以及 $Q$ 個操作，一開始文書編號 $i$ 在位置 $i$ 上。

  • 0 L R 反轉區間位置 $[L, R]$ 的文書
  • 1 x 詢問文書編號 $x$ 的位置

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
7 6
1 7
0 3 5
1 5
0 1 3
1 3
1 1
5 5
0 1 3
0 4 5
1 1
1 3
1 5
5 5
0 1 4
0 2 5
1 1
1 3
1 5

Sample Output

1
2
3
4
5
6
7
8
9
10
7
3
5
3
3
1
4
3
5
2

Solution

不能直接建造 $O(N)$ 的節點的 Splay tree，每一個節點為一個區間，每一次詢問最多產生兩個新的節點，空間為 $O(Q)$，時間複雜度為 $O(Q \log Q)$。而在詢問位置時，額外建造一個平衡樹來完成反向映射找到位置。

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
179
180
181
182
#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 200005;
class SPLAY_TREE { // Splay Tree
public:
    static const int MAXN = 200005;
    struct Node {
        static Node *EMPTY;
        Node *ch[2], *fa;
        int rev/*, size*/;
        int L, R, LRsize;
        Node() {
            ch[0] = ch[1] = fa = NULL;
            rev = 0;
//			size = 1;
            L = 0, R = -1, LRsize = 0;
        }
        bool is_root() {
            return fa->ch[0] != this && fa->ch[1] != this;
        }
        void pushdown() {
            if (rev) {
                if (ch[0] != EMPTY)	ch[0]->rev ^= 1;
                if (ch[1] != EMPTY)	ch[1]->rev ^= 1;
                swap(ch[0], ch[1]), swap(L, R);
                rev ^= 1;
            }
        }
        void pushup() {
//			if (ch[0] != EMPTY)	ch[0]->pushdown();
//			if (ch[1] != EMPTY)	ch[1]->pushdown();
//			size = 1 + ch[0]->size + ch[1]->size;
            LRsize = i_size() + ch[0]->LRsize + ch[1]->LRsize;
        }
        inline int i_size() {
            if (this == EMPTY)	return 0;
            return max(R, L) - min(R, L) + 1;
        }
    } _mem[MAXN];
    
    int bufIdx;
    SPLAY_TREE::Node *root;
    map<int, Node*> S;
    SPLAY_TREE() {
        Node::EMPTY = &_mem[0];
        Node::EMPTY->fa = Node::EMPTY->ch[0] = Node::EMPTY->ch[1] = Node::EMPTY;
//		Node::EMPTY->size = 0;
        bufIdx = 1; 
    }
    void init() {
        bufIdx = 1;
        S.clear();
    }
    Node* newNode() {
        Node *u = &_mem[bufIdx++];
        *u = Node();
        u->fa = u->ch[0] = u->ch[1] = Node::EMPTY;
        return u;
    }
    void rotate(Node *x) {
        Node *y;
        int d;
        y = x->fa, d = y->ch[1] == x ? 1 : 0;
        x->ch[d^1]->fa = y, y->ch[d] = x->ch[d^1];
        x->ch[d^1] = y;
        if (!y->is_root())
            y->fa->ch[y->fa->ch[1] == y] = x;
        x->fa = y->fa, y->fa = x;
        y->pushup();
    }
    void deal(Node *x) {
        if (!x->is_root())	deal(x->fa);
        x->pushdown();
    }
    Node* find_rt(Node *x) {
        for (; x->fa != Node::EMPTY; x = x->fa);
        return x;
    }
    void splay(Node *x, Node *below) {
        if (x == Node::EMPTY)	return ;
        Node *y, *z;
        deal(x);
        while (!x->is_root() && x->fa != below) {
            y = x->fa, z = y->fa;
            if (!y->is_root() && y->fa != below) {
                if (y->ch[0] == x ^ z->ch[0] == y)
                    rotate(x);
                else
                    rotate(y);
            }
            rotate(x);
        }
        x->pushup();
        if (x->fa == Node::EMPTY)	root = x;
    }
    Node* build(int l, int r) {
        if (l > r)	return Node::EMPTY; 
        Node *t = newNode();
        t->L = l, t->R = r;
        t->fa = Node::EMPTY;
        t->pushup();
        root = t;
        S[min(l, r)] = t;
        return t;
    }
    Node *splitNode(int pos) {	// make node interval [pos, ?]
    	Node *u = root, *v;
    	for (int t; u != Node::EMPTY;) {
    		u->pushdown();
    		t = u->ch[0]->LRsize;
    		if (t+1 == pos)	return u; 
    		if (t >= pos) {
    			u = u->ch[0];
    		} else if (pos > t + u->i_size()) {
    			pos -= t + u->i_size(), u = u->ch[1];
    		} else {
                int l = u->L, r = u->R;
    			Node *x = newNode();
    			pos -= t;
    			S[min(u->L, u->R)] = u;
    			if (l < r)
    				u->L = l + (pos - 1), r = u->L - 1;
    			else
    				u->L = l - (pos - 1), r = u->L + 1;
    			x->L = l, x->R = r;
    			if (u->ch[0] == Node::EMPTY) {
    				u->ch[0] = x, x->fa = u;
    			} else {
    				v = prevNode(u);
    				v->ch[1] = x, x->fa = v;
    			}
    			S[min(u->L, u->R)] = u;
    			S[min(x->L, x->R)] = x;
    			splay(x, Node::EMPTY);
    			return u;
    		}
    	}
    }
    Node* prevNode(Node *u) {
    	splay(u, Node::EMPTY);
        for (u = u->ch[0]; u->pushdown(), u->ch[1] != Node::EMPTY; u = u->ch[1]);
        return u;
    }
    void reverse(int l, int r) {
    	Node *p, *q;
    	p = splitNode(l);
    	p = prevNode(p);
        q = splitNode(r+1);
    	splay(p, Node::EMPTY), splay(q, root);
    	q->ch[0]->rev ^= 1;
    	splay(q->ch[0], Node::EMPTY);
    }
    int find(int x) {
    	Node *u;
    	map<int, Node*>::iterator it;
        it = S.upper_bound(x), it--;
    	u = it->second;
    	splay(u, Node::EMPTY);
    	return u->ch[0]->LRsize + abs(x - u->L) + 1;
    }
} tree;
SPLAY_TREE::Node *SPLAY_TREE::Node::EMPTY;
int main() {
    int N, Q;
    int cmd, l, r, x;
    while (scanf("%d %d", &N, &Q) == 2) {
        tree.init();
        tree.build(0, N+1);	// value [0, N+1], index [1, N+2]
        for (int i = 0; i < Q; i++) {
            scanf("%d", &cmd);
            if (cmd == 0) {
                scanf("%d %d", &l, &r);
                tree.reverse(l+1, r+1);
            } else {
                scanf("%d", &x);
                printf("%d\n", tree.find(x) - 1);
            } 
        }
    }
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

b487. 變態史考古 錯誤報導篇

Problem

題目描述

隨著考古學者近幾年的研究，逐漸地分析出變態人類文化族群的祖先。同時也知道，每一代人會將其變態基因傳遞給下一代，而下一代的變態指數會比上一代多一。若子代有數個，每個子代帶有的變態性向會有所歧異。

每當新聞報導某個變態父子關係時，人們總會熱議某兩個變態的相似程度。口耳相傳的消息是不可信任的，現在給予事情發生的時間軸，請驗證人們口中的變態相似程度。

變態相似程度定義

$\textit{sim}(A, B) = \frac{\textit{dist}(\textit{Original}(A), \textit{LCA}(A, B)) \times 2}{\textit{dist}(\textit{Original}(A), A) + \textit{dist}(\textit{Original}(B), B)}$

其中 $\textit{Original}(A)$ 表示根據事實推測得到的最早源頭祖先，$\textit{dist}(A, B)$ 表示在樹狀圖中兩點的距離，$\textit{LCA}(A, B)$ 表示 $A, \; B$ 最小公共祖先 (Lowest Common Ancestor，簡稱 LCA)。

例如當前知道的祖先關係如下

1
2
3
4
5
6
7
    P
   / 
  Q
 / \
A   R
   /
  B
  • $\textit{Original}(A) = \textit{Original}(B) = P$，
  • $\textit{dist}(P, A) = 3, \; \textit{dist}(P, B) = 4, \; \textit{LCA}(A, B) = Q, \; \textit{dist}(Q, P) = 2$。
  • 最後 $\textit{sim}(A, B) = \frac{4}{7}$

不幸地，在新聞報導時會因為口誤而傳錯消息，例如在一開始報導 A 的祖先為 R，過了不久受到指責才修正回 A 的祖先為 Q，錯誤報導的氾濫使得程序檢驗要求有效率且有彈性。不少變態因為錯誤報導而造受批判波及，現在要求你協助檢驗受災程度，好讓那些變態向新聞組織申請賠償。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
5 11
news 4 3
news 3 2
sim 3 4
sim 3 5
news 2 1
news 5 3
sim 3 4
sim 4 5
news 4 2
sim 4 5
sim 4 4

Sample Output

1
2
3
4
5
6
4/5
-1
6/7
3/4
4/7
1/1

Solution

相對於 Zerojudge b486. 變態史考古 的動態版本，因此沒辦法離線處理，當然也許有更高招的對操作二分等方式。

用 Link/Cut Tree 這一類的動態樹結構來說，維護有向樹根資訊就相當簡單，接著就是利用 Link/Cut Tree 找 LCA(x, y)，先藉由 access(y), splay(y) 將 y 轉到樹根，再把 x 打通到樹根去，最後一個從虛邊接上樹根所在的 splay tree 上的就是 LCA(x, y)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Node* lca(Node *x, Node *y) {
    if (x == y)	return x;
    if (find(x) != find(y))
        return Node::EMPTY;
    Node *u, *v = Node::EMPTY, *LCA = Node::EMPTY;
    access(y), splay(y);
    for (u = x; u != Node::EMPTY; u = u->fa) {
        splay(u);
        if (u->fa == Node::EMPTY)
            LCA = u;
        u->ch[1] = v;
        v = u;
        v->pushup();
    }
    return LCA;
}

由於是有根樹，找路徑權重時要防止上下關係發生變化，因此呼叫 void mk_root(Node *u) 操作時，限定 u 一定要是樹根才行。找路徑權重的方式也類似找 LCA 的方法。

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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
#include <bits/stdc++.h> 
using namespace std;
class LCT { // Link-Cut Tree
public:
    static const int MAXN = 100005;
    struct Node {
        static Node *EMPTY;
        Node *ch[2], *fa;
        int rev;
        int size;
        Node() {
            ch[0] = ch[1] = fa = NULL;
            rev = 0; 
            size = 1;
        }
        bool is_root() {
            return fa->ch[0] != this && fa->ch[1] != this;
        }
        void pushdown() {
            if (rev) {
                ch[0]->rev ^= 1, ch[1]->rev ^= 1;
                swap(ch[0], ch[1]);
                rev ^= 1;
            }
        }
        void pushup() {
            if (this == EMPTY)	return ;
            size = 1;
            if (ch[0] != EMPTY)
                size += ch[0]->size;
            if (ch[1] != EMPTY)
                size += ch[1]->size;
        }
    } _mem[MAXN];
    
    int bufIdx;
    LCT() {
        Node::EMPTY = &_mem[0];
        Node::EMPTY->fa = Node::EMPTY->ch[0] = Node::EMPTY->ch[1] = Node::EMPTY;
        Node::EMPTY->size = 0;
        bufIdx = 1; 
    }
    void init() {
        bufIdx = 1;
    }
    Node* newNode() {
        Node *u = &_mem[bufIdx++];
        *u = Node();
        u->fa = u->ch[0] = u->ch[1] = Node::EMPTY;
        return u;
    }
    void rotate(Node *x) {
        Node *y;
        int d;
        y = x->fa, d = y->ch[1] == x ? 1 : 0;
        x->ch[d^1]->fa = y, y->ch[d] = x->ch[d^1];
        x->ch[d^1] = y;
        if (!y->is_root())
            y->fa->ch[y->fa->ch[1] == y] = x;
        x->fa = y->fa, y->fa = x;
        y->pushup(), x->pushup();
    }
    void deal(Node *x) {
        if (!x->is_root())	deal(x->fa);
        x->pushdown();
    }
    void splay(Node *x) {
        Node *y, *z;
        deal(x);
        while (!x->is_root()) {
            y = x->fa, z = y->fa;
            if (!y->is_root()) {
                if (y->ch[0] == x ^ z->ch[0] == y)
                    rotate(x);
                else
                    rotate(y);
            }
            rotate(x);
        }
        x->pushup();
    }
    Node* access(Node *u) {
        Node *v = Node::EMPTY;
        for (; u != Node::EMPTY; u = u->fa) {
            splay(u);
            u->ch[1] = v;
            v = u;
            v->pushup();
        }
        return v;
    }
    void mk_root(Node *u) {
        access(u)->rev ^= 1, splay(u);
    }
    void cut(Node *x, Node *y) {
        mk_root(x);
        access(y), splay(y);
        y->ch[0] = x->fa = Node::EMPTY;
    }
    Node* cut(Node *x) {
        Node *u, *v, *rt = find(x);
        mk_root(rt);
        access(x), splay(x);
        for (v = x->ch[0]; v->ch[1] != Node::EMPTY; v = v->ch[1]);
        x->ch[0]->fa = x->fa;
        x->fa = x->ch[0] = Node::EMPTY;
        return v;
    }
    void link(Node *x, Node *y) {
        mk_root(x);
        x->fa = y;
    }
    Node* find(Node *x) {
        for (x = access(x); x->pushdown(), x->ch[0] != Node::EMPTY; x = x->ch[0]);
        return x;
    }
    //
    Node* lca(Node *x, Node *y) {
        if (x == y)	return x;
        if (find(x) != find(y))
            return Node::EMPTY;
        Node *u, *v = Node::EMPTY, *LCA = Node::EMPTY;
        access(y), splay(y);
        for (u = x; u != Node::EMPTY; u = u->fa) {
            splay(u);
            if (u->fa == Node::EMPTY) {
                LCA = u;
//				u->ch[1]->push_add(c), v->push_add(c);
            }
            u->ch[1] = v;
            v = u;
            v->pushup();
        }
        return LCA;
    }
    int path(Node *x, Node *y) {
        int ret;
        Node *u, *v = Node::EMPTY;
        access(y), splay(y);
        for (u = x; u != Node::EMPTY; u = u->fa) {
            splay(u), u->pushdown();
            if (u->fa == Node::EMPTY) {
                ret = u->ch[1]->size + v->size;
            }
            u->ch[1] = v;
            v = u;
            v->pushup();
        }
        return ret;
    }
    inline int label(Node *x) {
        return x - _mem;
    }
} tree;
LCT::Node *LCT::Node::EMPTY;
LCT::Node *A[100005], *node_x, *node_rt;
int main() {
    int n, m, x, y, c, u, v;
    char cmd[8];
    while (scanf("%d %d", &n, &m) == 2) {
        tree.init();
        for (int i = 1; i <= n; i++)
            A[i] = tree.newNode();
        
        for (int i = 0; i < m; i++) {
            scanf("%s", cmd);
            if (cmd[0] == 'n') {		// link
                scanf("%d %d", &x, &y);
                tree.cut(A[x]);
                tree.link(A[x], A[y]);
            } else if (cmd[0] == 's') {	// sim
                scanf("%d %d", &x, &y);
                node_x = tree.lca(A[x], A[y]);
                int lca = tree.label(node_x);
                if (lca == 0) { 
                    puts("-1");
                } else {
                    node_rt = tree.find(A[lca]);
                    int p1, p2;
                    p1 = tree.path(A[x], A[y]) + 1;
                    p2 = tree.path(A[lca], node_rt) + 1;
                    int a = p2*2, b = p1 + p2*2 - 1, g;
                    g = __gcd(a, b), a /= g, b /= g;
                    printf("%d/%d\n", a, b);
                } 
            }
        }
    }
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

a481. 樹的維護

Problem

操作有三種

  • 1 x y 詢問樹路徑 x - y 經過的點權重和
  • 2 x w 修改 x 的點權為 w
  • 3 x y 將 x 父節點修改成 y

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
5
0 1
1 2
1 3
2 4
2 5
5
1 3 5
2 1 2
1 3 5
3 2 3
1 3 5

Sample Output

1
2
3
11
12
10

Solution

題目看起來是一個有根樹，由於權重落在點上，又由於父節點修改可以用額外數組紀錄，因此可以當作無向樹操作。

假設知道一條邊的兩端點 e(u, v)，進行 cut(u, v) 操作，不知道誰父誰子的切割時，可以轉兩次通到樹根，讓另一端點落在左子樹。

1
2
3
4
5
void cut(Node *x, Node *y) {
    mk_root(x);
    access(y), splay(y);
    y->ch[0] = x->fa = Node::EMPTY;
}

由於是無向樹，詢問路徑則藉由將其中一端變成根，接著藉由 access() 將路徑接到樹根，再藉由 splay() 轉到 splay tree 的根，此時帶權值就是路徑總和。

1
2
3
4
5
int sumPath(Node *x, Node *y) {
    mk_root(x);
    access(y), splay(y);
    return y->sum;
}
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
#include <bits/stdc++.h> 
using namespace std;
class LCT { // Link-Cut Tree
public:
    static const int MAXN = 131072;
    struct Node {
        static Node *EMPTY;
        Node *ch[2], *fa;
        int rev;
        int val, sum, size;
        Node() {
            ch[0] = ch[1] = fa = NULL;
            rev = 0;
            val = sum = size = 1;
        }
        bool is_root() {
            return fa->ch[0] != this && fa->ch[1] != this;
        }
        void pushdown() {
            if (rev) {
                ch[0]->rev ^= 1, ch[1]->rev ^= 1;
                swap(ch[0], ch[1]);
                rev ^= 1;
            }
        }
        void pushup() {
            sum = val, size = 1;
            if (ch[0] != EMPTY)
                sum += ch[0]->sum, size += ch[0]->size;
            if (ch[1] != EMPTY)
                sum += ch[1]->sum, size += ch[1]->size;
        }
        inline void push_deal(int c) {
            val = c;
            pushup();
        }
    } _mem[MAXN];
    
    int bufIdx;
    LCT() {
        Node::EMPTY = &_mem[0];
        Node::EMPTY->fa = Node::EMPTY->ch[0] = Node::EMPTY->ch[1] = Node::EMPTY;
        bufIdx = 1; 
    }
    void init() {
        bufIdx = 1;
    }
    Node* newNode() {
        Node *u = &_mem[bufIdx++];
        *u = Node();
        u->fa = u->ch[0] = u->ch[1] = Node::EMPTY;
        return u;
    }
    void rotate(Node *x) {
        Node *y;
        int d;
        y = x->fa, d = y->ch[1] == x ? 1 : 0;
        x->ch[d^1]->fa = y, y->ch[d] = x->ch[d^1];
        x->ch[d^1] = y;
        if (!y->is_root())
            y->fa->ch[y->fa->ch[1] == y] = x;
        x->fa = y->fa, y->fa = x;
        y->pushup(), x->pushup();
    }
    void deal(Node *x) {
        if (!x->is_root())	deal(x->fa);
        x->pushdown();
    }
    void splay(Node *x) {
        Node *y, *z;
        deal(x);
        while (!x->is_root()) {
            y = x->fa, z = y->fa;
            if (!y->is_root()) {
                if (y->ch[0] == x ^ z->ch[0] == y)
                    rotate(x);
                else
                    rotate(y);
            }
            rotate(x);
        }
        x->pushup();
    }
    void access(Node *u) {
        Node *v = Node::EMPTY;
        for (; u != Node::EMPTY; u = u->fa) {
            splay(u);
            u->ch[1] = v;
            v = u;
            v->pushup();
        }
    }
    void mk_root(Node *u) {
        access(u), splay(u);
        u->rev ^= 1;
    }
    void cut(Node *x, Node *y) {
        mk_root(x);
        access(y), splay(y);
        y->ch[0] = x->fa = Node::EMPTY;
    }
    void link(Node *x, Node *y) {
        mk_root(x);
        x->fa = y;
    }
    Node* find(Node *x) {
        access(x), splay(x);
        for (; x->ch[0] != Node::EMPTY; x = x->ch[0]);
        return x;
    }
    //
    void dealNode(Node *x, int c) {
        mk_root(x);
        x->push_deal(c);
    }
    int sumPath(Node *x, Node *y) {
        mk_root(x);
        access(y), splay(y);
        return y->sum;
    }
} tree;
LCT::Node *LCT::Node::EMPTY;
LCT::Node *A[131072], *node_x, *node_y;
int p[131072];
int main() {
    int n, m, x, y, c, u, v, cmd;
    while (scanf("%d", &n) == 1) {
        tree.init();
        for (int i = 1; i <= n; i++)
            A[i] = tree.newNode();
        
        for (int i = 1; i <= n; i++) {
            scanf("%d %d", &p[i], &y);
            if (p[i])
                tree.link(A[i], A[p[i]]);
            tree.dealNode(A[i], y);
        }
        
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &cmd, &x, &y);
            if (cmd == 1) {
                printf("%d\n", tree.sumPath(A[x], A[y]));
            } else if (cmd == 2) {
                tree.dealNode(A[x], y);
            } else if (cmd == 3) {
                tree.cut(A[x], A[p[x]]);
                tree.link(A[x], A[y]);
                p[x] = y;
            }
        }
    }
    return 0;
}
Read More +