解題區/解題區 - 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 +
解題區/解題區 - 其他題目

2016 Google APAC Test 小結

不知道有這場比賽，無聊寫寫靜靜心。

A. Googol String

給定一個遞迴生成式，求 $S_{100}$ 的第 $n$ 位字符為何。

直接用遞迴返回去計算即可，狀態分別為 f(n, S_m, switch_flag)，如果超過 $S_{m-1}$ 的一半時，由於操作需要字串反轉，反向求位數和反轉操作即可。

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;
const int MAXN = 128;
unsigned long long b2[MAXN];
int f(long long n, int m, int s) {
    if (m == 1)	return s;
    if (n <= b2[m-1])
        return f(n, m-1, s);
    if (n == b2[m-1]+1)
        return s;
    return f(b2[m-1]-(n-b2[m-1]-1)+1, m-1, !s);
}
int main() {
    b2[0] = 0;
    for (int i = 1; i < MAXN; i++)
        b2[i] = (b2[i-1]<<1)+1;
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        long long n;
        scanf("%lld", &n);
        printf("Case #%d: ", ++cases);
        for (int i = 0; i < MAXN; i++) {
            if (b2[i] >= n) {
                printf("%d\n", f(n, i, 0));
                break;
            }
        }
    }
    return 0;
}

B. gCube

有一個 ? 維空間，要抓數列區間 [L, R]內的數字，構成 R-L+1 的超長方體，請問等體積下的超正方體的邊長為何。

簡單地說要把區間內的數字相乘起來，並且開 n 次根，由於乘數結果會 overflow，套用 log() 來完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 128;
unsigned long long b2[MAXN];
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int n, m, A[1024], x, y;
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        printf("Case #%d:\n", ++cases);
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            double sum = 0;
            for (int j = x; j <= y; j++)
                sum += log(A[j]);
            sum /= (y - x + 1);
            printf("%.9lf\n", exp(sum));
        }
    }
    return 0;
}

C. gCampus

辦公室之間有一些道路，每一個道路通過會消耗時間，請問那些沒效率的邊不在任兩個辦公室的最短路徑上。

看起來是能直接丟 floyd algorithm，由於 $|V| \le 100$，只需要窮舉邊兩個端點的經過的最短路徑，複雜度為 $O(V^3 + E V^2)$，仔細看一下還挺大的。

套用單源短路徑 SSSP 的做法，對每一個點都跑一次 dijkstra，檢查 shortest path DAG，複雜度需要 $O(V E \log V)$，點數有點太小 (再大也不方便處理)，大約在數秒內就能跑完。

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;
const int MAXV = 32767;
const int MAXE = 32767;
const long long INF = 1LL<<62;
struct Edge {
    int to, eid;
    long long w;
    Edge *next;
};
Edge edge[MAXE], *adj[MAXV];
int e = 0;
long long dist[MAXV];
void addEdge(int x, int y, long long v)  {
    edge[e].to = y, edge[e].w = v, edge[e].eid = e;
    edge[e].next = adj[x], adj[x] = &edge[e++];
}
void dijkstra(int st, long long dist[], int n) {
typedef pair<long long, int> PLL;
    for (int i = 0; i <= n; i++)
        dist[i] = INF;
    set<PLL> pQ;
    PLL u;
    pQ.insert(PLL(0, st)), dist[st] = 0;
    while (!pQ.empty()) {
        u = *pQ.begin(), pQ.erase(pQ.begin());
        for (Edge *p = adj[u.second]; p; p = p->next) {
            if (dist[p->to] > dist[u.second] + p->w) {
                if (dist[p->to] != INF)
                    pQ.erase(pQ.find(PLL(dist[p->to], p->to)));
                dist[p->to] = dist[u.second] + p->w;
                pQ.insert(PLL(dist[p->to], p->to));
            }
        }
    }
}
int main() {
    int testcase, cases = 0, n, m;
    int x, y, w;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        
        e = 0;
        for (int i = 0; i <= n; i++)
            adj[i] = NULL;
            
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &x, &y, &w);
            addEdge(x, y, w);
            addEdge(y, x, w);
        }
        
        int on[65536] = {};
        for (int i = 0; i < n; i++) {
            dijkstra(i, dist, n);
            for (int j = 0; j < n; j++) {
                for (Edge *p = adj[j]; p; p = p->next) {
                    if (dist[p->to] == dist[j] + p->w)
                        on[p->eid/2] = 1;
                }
            }
        }
        printf("Case #%d:\n", ++cases);
        for (int i = 0; i < m; i++) {
            if (!on[i])
                printf("%d\n", i);
        }
    }
    return 0;
}

D. gSnake

一個貪心蛇遊戲，一開始蛇在左上角長度為 1，並且面向右側。若盤面上黑白染色，所有的奇點都具有食物，每一秒蛇會執行一個動作，直到他咬到自己的身體為止。當蛇碰撞到牆壁時，他會從對稱的地方鑽出。而下一秒接觸到食物時，相當於頭往前直伸產生新的一節。

現在有一串指令，每一個指令告知蛇會在那一秒後，執行順時針或逆時針轉向，請問模擬指令直到死亡或者抵達 $10^9$ 秒，請問蛇的總長為何。

這一題看起來有點可怕，由於貪心蛇所在的棋盤大小偌大無比，導致模擬上複雜度難以估計，但仔細發現指令時間最多 $1 \le X_i \le 1000000$，意即 $10^6$ 秒將會固定方向，在這固定方向模擬，最多吃到 max(R, C) 的食物，接著進入鑽出鑽出的循環狀態，或者進入終盤死亡。

根據循環和模擬情況加總，最多 $O(1000000)$ 步。為了解決偵測，用一個 map< pair<X, Y>, int > 來記錄身體經過的時間點，只要時間點差小於身體總長，表示咬到自己。或者，實做一個 list，維護一個 set< pair<X, Y> > 將頭端插入，移動時將尾巴移除。前者時間複雜度 $O(n \log n)$ 其中 $n = 1000000$，後者跟自身長度有關，但實作稍微複雜。

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
#include <bits/stdc++.h> 
using namespace std;
const int MAXS = 100005;
const int MAXT = 10e9;
const int dx[4] = {0, 1, 0, -1};	// right, down, left, up
const int dy[4] = {1, 0, -1, 0};
int X[MAXS];
char CMD[MAXS][4];
int main() {
    int testcase, cases = 0, R, C, S;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &S, &R, &C);
        for (int i = 0; i < S; i++)
            scanf("%d %s", &X[i], &CMD[i]);
            
        int len = 1, x = 1, y = 1, dir = 0;
        int cmdIdx = 0, cnt = 0;
        
        set< pair<int, int> > F;
        map< pair<int, int>, int > PASS;
        
        for (int i = 1; i <= MAXT; i++) {
            if (cmdIdx == S && cnt > max(R, C)*2)	// cycle
                break;
            x += dx[dir], y += dy[dir];
            if (x == 0)	x = R;
            if (x > R)	x = 1;
            if (y == 0)	y = C;
            if (y > C)	y = 1;
            
            int &step = PASS[{x, y}]; 
            if (step == 0)	step = -0x3f3f3f3f;
            if (i - step < len)
                break;
            step = i;			
            
            if ((x+y)%2 == 1 && !F.count({x, y})) {
                F.insert({x, y});
                len++, cnt = 0;
            }
            
            if (cmdIdx < S && i == X[cmdIdx]) {
                if (CMD[cmdIdx][0] == 'R')
                    dir = (dir+1)%4;
                else
                    dir = (dir+3)%4;
                cmdIdx++, cnt = 0;
            }
            cnt++;
        }
        printf("Case #%d: %d\n", ++cases, len);
    }
    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 +
解題區/解題區 - 其他題目

PTC 201508 八月小結

由於代碼有點長，所以就放在 Github 上進行瀏覽，在此只提供文字說明，題解代碼 點我。

現在還沒提供 OJ 線上測試，不保證代碼和算法的正確性。

Problem A Date Matching Problem

在一個二分帶權匹配問題中，模擬近似解的做法：每一次挑選權值最大的兩個未配對男女，請問最後得到的帶權匹配最大為何。

純粹模擬，沒有要求最大帶權匹配，最大帶權匹配可以用 KM 算法或者是最少費用流去完成。題目沒說明權重是否有相同情況，那麼模擬結果可能會有點問題在。

Problem B Community Detection in Social Media

在社群媒體中，用節點表示一個個體，節點和節點之間會有所關連，這時候用一條邊連接起來，邊上用權重大小表示關聯強度。現在要將這 $N$ 個節點分成恰好 $K$ 群，每一個節點只能分配到一個群集中，為了使得分群效果更好，定義分群的好壞程度，對於任意兩點若有一條邊且在不同群，則這些點對的邊權重最大值就是分群評價，這個評價分數越低越好，意即群之間的相似度越低越好。請求出分群評價最低為何。

貪心，按照邊權由大排到小，接著使用 disjoint set 並查集來合併，直到低於 K 群，此時的邊權就是答案。

Problem C Treasure

Alice 和 Bob 這對狗男女 又在玩遊戲，他們要分 $N$ 個寶物，每個寶物到兩個人手上的價值都不同，同時分配寶物的個數最多只能差 1，請問最少分配價值差的絕對值為何。

由於 $N \le 35$，直接窮舉 $O(2^N)$ 消耗時間，於是可以剖半搜索，類似中間相遇法，窮舉前一半、後一半的所有組合，接著二分去合併，時間複雜度 $O(2^{N/2} N)$。特別小心寶物數量只能差 1，需要窮舉其中一個人的分配數量、計算組合時紀錄其中一個人的個數。

Problem D Coloring Statues

夜晚不死之神－夜神月，由於他太無聊，決定去更改院子裡的雕像顏色，顏色只有黑白兩種，他會玩到所有雕像顏色都為黑色時停止，請問 $K$ 天之後黑色雕像的顏色數。

$N$ 個雕像排成一列，各自擁有初始化的顏色，每一天的規則如下

所有雕像顏色為黑色就停止操作 更改最左側的雕像顏色，滿足前面所有操作都不重複的狀態，並且結束這一天。
* 一天只能改一個雕像，並將黑色改白色、白色改黑色。

變化的格雷碼計算，$N, \; K$ 非常大，不能用遞迴慢慢窮舉。那麼就 wiki 得到計算方法。

1
2
3
4
5
6
7
8
9
10
unsigned int binaryToGray(unsigned int num) {
    return (num >> 1) ^ num;
}
unsigned int grayToBinary(unsigned int num) {
    unsigned int mask;
    for (mask = num >> 1; mask != 0; mask = mask >> 1) {
        num = num ^ mask;
    }
    return num;
}

主要核心為這兩個二進制和格雷碼的相互轉換，需要運用二進制的大數操作，只有位移、XOR、加法模擬，代碼的複雜程度可以接受。特別小心，由於雕像一開始有初始狀態，最終盤面 (全黑) 與格雷碼實際會有所不同，需要做每一個位置的黑白交換，否則不能滿足與前幾天都不重複的狀態。

用大數方法模擬上面兩個函數，並且在加法運算和最終盤面之間偵測 overflow 即可，時間複雜度 $O(N^2)$。

Problem E CPU

多核心排程問題，有 $C$ 個 CPU，每一個 CPU 可以用 $K$ 種不同的效能去完成工作，選擇哪一種效能會反映在處理時間$T_i$ 和電量消耗$E_i$，不同顆 CPU 的情況也各自不同，但它們可以平行工作。現在要安排 $N$ 份工作，每一個工作有 $I$ 個單位指令，不用考慮先做後做的順序，一旦他們進入排入 CPU，則一定會做完才能排定下一份工作。

每一個工作指派到 CPU 上會有處理的周轉時間 $Tu$ (turnaround time) 和能量消耗 $E$ (enery cost)，給定兩個常數$R_t, \; R_e$ 分別為總評價的參數，目標使得$\sum Tu_i R_t + E_i R_e$ 最小。

把$R_t, \; R_e$ 直接反應到效能和電量消耗，融進去之後就不用考慮。

首先，解決單一個 CPU 操作如何解決排程問題，藉由預先支付來解決週期時間 (turnaround time) 的計算，因此剩餘工作有 $R$ 個時，若要選入$Job_i$ 且使用 CPU 的第 $j$ 個方案，花費為$I_i \times R \times T_i + I_i \times E_i$，預先支付剩下 $R$ 個工作會增加的量，每一次抓最小的工作進行安排，樸素實作需要 $O(N^2 K)$。

從數學公式看出來，指令個數$I_i$ 可以提出，觀察一下，就是最短工作優先 (SJF) 的想法讓 turnaround time 總和最小，排序指令數量由小到大安排即可，複雜度降至 $O(N \log N + NK)$。

接著，考慮多核心情況，由於不知一個核心有多少個工作，無法預先支付接下來的工作成本，但 SJF 的思路仍然成立，即在每一個核心中，工作順序仍然是按照指令數量由小到大依序做。為了解決無法支付的問題，反向安排工作，決定最後一個工作要分配到哪一個 CPU，對於安排工作去找到 CPU 的成本$\text{CPUjob}_i \times T_i + E_i$ 最小，並且累計那一個 CPU 已經安排多少個工作$\text{CPUjob}_i$，複雜度降至 $O(N \log N + N (K + \log C))$

Read More +
解題區/解題區 - UVa

UVa 11996 - Jewel Magic

Problem

給定一個字串，支持以下四種操作

  • 1 p c 插入一個字符 c 在位置 p
  • 2 p 刪除位置 p 的字符
  • 3 p1 p2 反轉區間 [p1, p2]
  • 4 p1 p2 求出子字串的 LCP 最常共同前綴長。

Sample Input

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

Sample Output

1
2
3
4
5
6
3
6
2
0
3
2

Solution

前三項很簡單地可以運用一些 treap 和 splay tree 完成，對於第四項則比較麻煩，只能靠二分長度 + hash 操作來完成。

splay tree 中每一個節點表示一個字符，因此中序走訪就是原本的字串。由於需要反轉操作，需要維護反轉標記，由於要維護 hash 值，需要額外維護一個前綴 hash 值，由於搭配反轉標記，必要時維護後綴 hash 值 (逆序)。

二分 LCP 長度時，就相當於把某個區間從 splay tree 剪下，然後看根的 hash 結果。由於之後還要接回去，實作時利用 splay() 操作，把區間的前一個和後一個節點轉到根和根之下，則區間則會在根的右子樹的左子樹，由於會運用到區間的前一個和後一個，因此維護兩個哨兵字符在字串中 $000001# 方便空節點的判斷。

關於 hash 部分，由於要有點數學合成，不知道一些奇怪的雜湊怎麼用在二元樹長度不固定的接合，可以利用多項式 hash(string) = s0 + s1 x + s2 x^2 + ... 來完成，讓他自動溢位即可，至於 x 的基底就隨便挑吧！

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
#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 400005;
const int SEED = 13;
unsigned long BASE[MAXN];
class SPLAY_TREE { // Splay Tree
public:
    static const int MAXN = 400005;
    struct Node {
        static Node *EMPTY;
        Node *ch[2], *fa;
        int rev;
        int val, size;
        unsigned long h[2];
        Node() {
            ch[0] = ch[1] = fa = NULL;
            rev = 0;
            val = 0, size = 1;
            h[0] = h[1] = 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(h[0], h[1]);
                rev ^= 1;
            }
        }
        void pushup() {
            if (ch[0] != EMPTY)	ch[0]->pushdown();
            if (ch[1] != EMPTY)	ch[1]->pushdown();
            h[0] = ch[0]->h[0] + val*BASE[ch[0]->size] + ch[1]->h[0]*BASE[ch[0]->size+1];
        	h[1] = ch[1]->h[1] + val*BASE[ch[1]->size] + ch[0]->h[1]*BASE[ch[1]->size+1];
            size = 1 + ch[0]->size + ch[1]->size;
        }
    } _mem[MAXN];
    
    int bufIdx;
    SPLAY_TREE::Node *root;
    SPLAY_TREE() {
        Node::EMPTY = &_mem[0];
        Node::EMPTY->fa = Node::EMPTY->ch[0] = Node::EMPTY->ch[1] = Node::EMPTY;
        Node::EMPTY->size = Node::EMPTY->val = 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();
    }
    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) {
        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, Node *p, char s[]) {
        if (l > r)	return Node::EMPTY; 
        int mid = (l + r)/2;
        Node *t = newNode();
        t->val = s[mid], t->fa = p;
        t->ch[0] = build(l, mid-1, t, s);
        t->ch[1] = build(mid+1, r, t, s);
        t->pushup();
        if (p == Node::EMPTY)	root = t;
        return t;
    }
    void debug(Node *u){
        if (u == Node::EMPTY) return;
        u->pushdown();
        debug(u->ch[0]);
        printf("%d", u->val);
        debug(u->ch[1]);
    }
    Node* kthNode(int pos) {
    	Node *u = root;
    	for (int t; u != Node::EMPTY;) {
    		u->pushdown();
    		t = u->ch[0]->size;
    		if (t+1 == pos)	return u;
    		if (t >= pos)
    			u = u->ch[0];
    		else
    			pos -= t+1, u = u->ch[1];
    	}
    	return Node::EMPTY;
    } 
    void insert(int pos, int val) {
    	Node *p, *q, *r;
    	p = kthNode(pos), q = kthNode(pos+1);
    	r = newNode();
    	splay(p, Node::EMPTY);
    	splay(q, root);
    	r->val = val, q->ch[0] = r, r->fa = q;
    	splay(r, Node::EMPTY);
    }
    void erase(int pos) {
    	Node *p, *q;
    	p = kthNode(pos-1), q = kthNode(pos+1);
    	splay(p, Node::EMPTY), splay(q, root);
    	q->ch[0] = Node::EMPTY;
    	splay(q, Node::EMPTY);
    }
    void reverse(int l, int r) {
    	Node *p, *q;
    	p = kthNode(l-1), q = kthNode(r+1);
    	splay(p, Node::EMPTY), splay(q, root);
    	q->ch[0]->rev ^= 1;
    	splay(q->ch[0], Node::EMPTY);
    }
    unsigned long hash(int l, int r) {
    	Node *p, *q;
    	p = kthNode(l-1), q = kthNode(r+1);
    	splay(p, Node::EMPTY), splay(q, root);
    	return q->ch[0]->h[0];
    }
    int lcp(int l, int r) {
    	int ret = 0;
    	int bl = 1, br = root->size - max(l, r), mid;
    	while (bl <= br) {
    		mid = (bl + br)/2;
    		if (hash(l, l+mid-1) == hash(r, r+mid-1))
    			bl = mid+1, ret = mid;
    		else
    			br = mid-1;
    	}
    	return ret;
    }
} tree;
SPLAY_TREE::Node *SPLAY_TREE::Node::EMPTY;
int main() {
    BASE[0] = 1;
    for (int i = 1; i < MAXN; i++)
        BASE[i] = BASE[i-1] * SEED;
    int n, m;
    int cmd, p, c, p1, p2;
    char s[262144];
    while (scanf("%d %d", &n, &m) == 2) {
        scanf("%s", s+1);
        s[0] = 3, s[n+1] = 4;
        for (int i = 1; i <= n; i++)
            s[i] -= '0';
        tree.init();
        tree.build(0, n+1, SPLAY_TREE::Node::EMPTY, s);
        for (int i = 0; i < m; i++) {
            scanf("%d", &cmd);
            if (cmd == 1) {
                scanf("%d %d", &p, &c);
                tree.insert(p+1, c);
            } else if (cmd == 2) {
                scanf("%d", &p);
                tree.erase(p+1);
            } else if (cmd == 3) {
                scanf("%d %d", &p1, &p2);
                tree.reverse(p1+1, p2+1);
            } else if (cmd == 4) {
                scanf("%d %d", &p1, &p2);
                int t = tree.lcp(p1+1, p2+1);
                printf("%d\n", t);
            } 
//    		tree.debug(tree.root);
//			puts("");
        }
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11994 - Happy Painting

Problem

操作有三種

  • 1 x y c 將 x 的父親修改成 y，並且這一條邊的顏色為 c
  • 2 x y c 將 x 到 y 的路徑上的邊都修改成顏色 c
  • 3 x y 回報路徑 x 到 y 上有幾種顏色。

Sample Input

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

Sample Output

1
2
3
4
2 2
1 1
0 0
4 3

Solution

顏色總數不超過 30 種，因此可以使用位元壓縮。這題是之前寫的，所以在找同類的父子關係沒有弄好，可以使用 LCA 去代替那繁複的操作，請參照前幾篇的 Link/Cut Tree 的代碼。

這題很特別的地方在於邊權，由於是有根樹，每個節點的點權可以表示成連接父親的邊權，操作時要特別小心，計算路徑時，不可讓上下父子關係顛倒，否則點權會失效，只有樹根才能使用 mk_root。同樣地，找一條路徑 (x, y) 時，先打通 y 到樹根的路徑，接著把 x 打通到樹根的同時，會到最後一次打通時，會碰到 LCA(x, y)，接著將其路徑上的數值合併。

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
#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, lazy, sum, size;
        Node() {
            ch[0] = ch[1] = fa = NULL;
            rev = 0;
            val = sum = 0, size = 1;
            lazy = 0;
        }
        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;
            }
            if (lazy != 0) {
                if (ch[0] != EMPTY)	ch[0]->push_add(lazy);
                if (ch[1] != EMPTY)	ch[1]->push_add(lazy);
                lazy = 0;
            }
        }
        void pushup() {
            if (this == EMPTY)	return ;
            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) {
            if (this == EMPTY)	return ;
            val = c;
        }
        inline void push_add(int c) {
            if (this == EMPTY)	return ;
            val = sum = c;
            lazy = c;
        }
    } _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 *rt, Node *x) {
        Node *u, *v;
        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;
    }
    //
    void alter(Node *x, Node *y, int c) {
        if (x == y)		return ;
        Node *rt = find(x), *fx = Node::EMPTY;
        if (rt != x)
            fx = _cut(rt, x);
        if (x == find(y)) {	// resume
            if (fx != Node::EMPTY)
                link(x, fx);
        } else {
            link(x, y);
            x->push_deal(c);
        }
    }
    void paint(Node *x, Node *y, int c) {
        if (x == y || find(x) != find(y))
            return ;
        Node *u, *v = Node::EMPTY;
        access(y), splay(y);
        for (u = x; u != Node::EMPTY; u = u->fa) {
            splay(u);
            if (u->fa == Node::EMPTY) {
                u->ch[1]->push_add(c), v->push_add(c);
            }
            u->ch[1] = v;
            v = u;
            v->pushup();
        }
    }
    pair<int, int> orPath(Node *x, Node *y) {
        if (x == y || find(x) != find(y))
            return {0, 0};
        pair<int, 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]->sum | v->sum};
            }
            u->ch[1] = v;
            v = u;
            v->pushup();
        }
        return ret;
    }
    void debug(int n) {
        for (int i = 1; i <= n; i++)
            printf("[%2d] l %2d r %2d fa %2d rev %2d, val %d lazy %d, %d\n", i, _mem[i].ch[0] - _mem, 
                                                    _mem[i].ch[1] - _mem,
                                                    _mem[i].fa - _mem, 
                                                    _mem[i].rev,
                                                    __builtin_ffs(_mem[i].val)-1,
                                                    __builtin_ffs(_mem[i].lazy)-1,
                                                    _mem[i].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 %d", &n, &m) == 2) {
        tree.init();
        for (int i = 1; i <= n; i++)
            A[i] = tree.newNode();
        
        for (int i = 1; i <= n; i++) {
            scanf("%d", &p[i]);
            if (p[i])
                A[i]->fa = A[p[i]];
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d", &c);
            if (p[i])
                A[i]->push_deal(1<<c);
        }
        
        for (int i = 0; i < m; i++) {
            scanf("%d", &cmd);
            if (cmd == 1) {
                scanf("%d %d %d", &x, &y, &c);
                tree.alter(A[x], A[y], 1<<c);
            } else if (cmd == 2) {
                scanf("%d %d %d", &x, &y, &c);
                tree.paint(A[x], A[y], 1<<c);
            } else if (cmd == 3) {
                scanf("%d %d", &x, &y);
                pair<int, int> r = tree.orPath(A[x], A[y]);
                printf("%d %d\n", r.first, __builtin_popcount(r.second));
            }
        }
    }
    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 +