解題區/解題區 - UVa

UVa 1479 - Graph and Queries

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給 N 個點、M 條邊的無向圖，現在有三種操作：

  • D X ：刪除輸入編號 X 的邊
  • Q X K ：詢問與 X 相同連通元件中，節點權重第 K 大。
  • C X V ：將節點 X 權重修改成 V。

Sample Input

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
3 3 
10 
20 
30 
1 2 
2 3 
1 3 
D 3 
Q 1 2 
Q 2 1 
D 2 
Q 3 2 
C 1 50
Q 1 1
E
3 3 
10 
20 
20 
1 2 
2 3 
1 3 
Q 1 1 
Q 1 2 
Q 1 3 
E 
0 0

Sample Output

1
2
Case 1: 25.000000 
Case 2: 16.666667

Solution

可以看出，如果順著做會比較繁瑣，分裂總是比合併來的痛苦，根據并查集的概念，將其變成合併操作。

我們逆著輸入順序處理，根據離線的方式，可以預測最後會分裂到甚麼情況、最後某個節點帶什麼權重，分別將其建造一個平衡樹。刪除一條邊相當於加入一條邊，并查集看出好比兩個平衡樹合併，修改一個節點權重相當於回朔前一個版本的值。

而要在平衡樹中查找第 k 大元素不能用 STL，這裡用比較簡單的 treap，編程複雜度比較低。

treap 的效率取決於每個節點攜帶的隨機權重，事先用內存池撒過一次亂數，之後需要再從內存池提取，之後就不撒亂數，蛋疼的是竟然活生生掛掉了。還是乖乖 srand(514); 偷懶不想用 new 加快效率什麼的，實在囧

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define MAXN 65536
#define MAXM 65536
#define MAXQ (1<<20)
struct node;
node *null;
struct node {
    node *lson, *rson;
    int key, value, size;
    
    node(int x = 0, int s = 1):key(x), size(s) {
        lson = rson = null;
    }
    void update() {
        if (this != null)
            size = lson->size + rson->size + 1;
    }
} nodes[MAXQ], *root[MAXN];
struct treap {
    int bufIdx;
    node *getNode(int val) {
        node *ret = &nodes[bufIdx++];
        *ret = node(val);
        ret->value = rand();
        return ret;
    }
    void rotate(node* &a, int dir) { // dir {0: left, 1: right}
        node *p;
        if (dir == 0) {
            p = a->rson;
            a->rson = p->lson;
            p->lson = a;
        } else {
            p = a->lson;
            a->lson = p->rson;
            p->rson = a;
        }
        a->update(), p->update();
        a = p;
    }
    void insert(node* &a, int val) {
        if (a == null)
            a = getNode(val);
        else {
            if (val < a->key) {
                insert(a->lson, val);
                if (a->lson->value > a->value)
                    rotate(a, 1);
            } else {
                insert(a->rson, val);
                if (a->rson->value > a->value)
                    rotate(a, 0);
            }
        }
        a->update();
    }
    void remove(node* &a, int val) {
        if (a->key == val) {
            if (a->lson == null)
                a = a->rson;
            else if (a->rson == null)
                a = a->lson;
            else {
                if (a->lson->value > a->rson->value)
                    rotate(a, 1), remove(a->rson, val);
                else
                    rotate(a, 0), remove(a->lson, val);
            }
        } else if (val < a->key) {
            remove(a->lson, val);
        } else {
            remove(a->rson, val);
        }
        a->update();
    }
    void merge(node* &from, node* &to) {
        if (from->lson != null)
            merge(from->lson, to);
        if (from->rson != null)
            merge(from->rson, to);
        insert(to, from->key); // delete node `from`, need use delete replace pool.
    }
    node* kth_element(node* &a, int k) {
        if (a == null || k <= 0 || k > a->size)	return null;
        if (k == a->lson->size + 1)
            return a;
        if (k <= a->lson->size)
            return kth_element(a->lson, k);
        else
            return kth_element(a->rson, k - a->lson->size - 1);
    }
    node* rkth_element(node* &a, int k) {
        if (a == null || k <= 0 || k > a->size)	return null;
        if (k == a->rson->size + 1)
            return a;
        if (k <= a->rson->size)
            return rkth_element(a->rson, k);
        else
            return rkth_element(a->lson, k - a->rson->size - 1);
    }
    int lower_dist(node* &a, int val) {
        if (a == null)	return 1;
        if (a->value < val)
            return a->lson->size + 1 + lower_dist(a->rson, val);
        else
            return lower_dist(a->lson, val);
    }
    int upper_dist(node* &a, int val) {
        if (a == null)	return 1;
        if (a->value > val)
            return a->rson->size + 1 + upper_dist(a->lson, val);
        else
            return upper_dist(a->rson, val);
    }
    void print(node *ver) {
        if (ver == null)	return;
        print(ver->lson);
        printf("print %d %d\n", ver->key, ver->size);
        print(ver->rson);
    }
    void init() {
        bufIdx = 0;
        null = &nodes[bufIdx++];
        null->size = 0, null->lson = null->rson = null, null->value = 0;
    }
} tree;
char cmd[MAXQ][4];
int QX[MAXQ], QY[MAXQ], edgeX[MAXM], edgeY[MAXM], w[MAXN];
int parent[MAXN], weight[MAXN];
int findp(int x) {
    return parent[x] == x ? x : (parent[x] = findp(parent[x]));
}
void joint(int x, int y) {
    x = findp(x), y = findp(y);
    if (x == y)	return;
    if (weight[x] > weight[y]) {
        parent[y] = x, weight[x] += weight[y];
        tree.merge(root[y], root[x]);
        
    } else {
        parent[x] = y, weight[y] += weight[x];
        tree.merge(root[x], root[y]);
    }
}
void initDisjointSet(int n)  {
    for (int i = 1; i <= n; i++)
        parent[i] = i, weight[i] = 1;
}
void changeVertex(int u, int val) {
    int r = findp(u);
    tree.remove(root[r], w[u]);
    tree.insert(root[r], val);
    w[u] = val;
}
int main() {
    //    freopen("in.txt", "r+t", stdin);
    //    freopen("out.txt", "w+t", stdout);
    int n, m, q, t;
    int cases = 0;
    while (scanf("%d %d", &n, &m) == 2 && n) {
        tree.init();
        for (int i = 1; i <= n; i++)
            scanf("%d", &w[i]);
        for (int i = 1; i <= m; i++)
            scanf("%d %d", &edgeX[i], &edgeY[i]);
        int exists[MAXM] = {};
        for (int i = 1; i <= m; i++)
            exists[i] = 1;
        for (q = 0; scanf("%s", cmd[q]) == 1 && cmd[q][0] != 'E'; q++) {
            if (cmd[q][0] == 'D')
                scanf("%d", &QX[q]), exists[QX[q]] = 0;
            else if (cmd[q][0] == 'C')
                scanf("%d %d", &QX[q], &QY[q]), t = QY[q], QY[q] = w[QX[q]], w[QX[q]] = t;
            else if (cmd[q][0] == 'Q')
                scanf("%d %d", &QX[q], &QY[q]);
        }
        
        for (int i = 1; i <= n; i++)
            root[i] = null;
        for (int i = 1; i <= n; i++)
            tree.insert(root[i], w[i]);
        initDisjointSet(n);
        for (int i = 1; i <= m; i++)
            if (exists[i] == 1)
                joint(edgeX[i], edgeY[i]);
        
        double ret = 0, cnt = 0;
        for (int i = q - 1; i >= 0; i--) {
            if (cmd[i][0] == 'D')
                joint(edgeX[QX[i]], edgeY[QX[i]]);
            else if (cmd[i][0] == 'C')
                changeVertex(QX[i], QY[i]);
            else if (cmd[i][0] == 'Q') {
                cnt++;
                node* v = tree.rkth_element(root[findp(QX[i])], QY[i]);
                if (v == null)	/*puts("undefined")*/;
                else 			ret += v->key/*, printf("kth %d\n", v->key)*/;
            }
        }
        ret /= cnt;
        printf("Case %d: %lf\n", ++cases, ret);
    }
    return 0;
}
/*
 3 3
 10
 20
 30
 1 2
 2 3
 1 3
 D 3
 Q 1 2
 Q 2 1
 D 2
 Q 3 2
 C 1 50
 Q 1 1
 E
 */