Graph and Queries(Splay启发式合并)

描述

You are given an undirected graph with $N$ vertexes and $M$ edges. Every vertex in this graph has an integer value assigned to it at the beginning. You’re also given a sequence of operations and you need to process them as requested. Here’s a list of the possible operations that you might encounter:

  1. Deletes an edge from the graph.
    The format is [D X], where $X$ is an integer from $1$ to $M$, indicating the ID of the edge that you should delete. It is guaranteed that no edge will be deleted more than once.
  2. Queries the weight of the vertex with $K$-th maximum value among all vertexes currently connected with vertex $X$ (including $X$ itself).
    The format is [Q X K], where X is an integer from $1$ to $N$, indicating the id of the vertex, and you may assume that $K$ will always fit into a 32-bit signed integer. In case $K$ is illegal, the value for that query will be considered as undefined, and you should return $0$ as the answer to that query.
  3. Changes the weight of a vertex.
    The format is [C X V], where $X$ is an integer from $1$ to $N$, and $V$ is an integer within the range $[-10^6, 10^6]$.

The operations end with one single character, $E$, which indicates that the current case has ended.
For simplicity, you only need to output one real number - the average answer of all queries.

Input

There are multiple test cases in the input file. Each case starts with two integers $N$ and $M$ ($1 ≤ N ≤ 2 * 10^4$, $0 ≤ M ≤ 6 * 10^4$), the number of vertexes in the graph. The next $N$ lines describes the initial weight of each vertex ($-10^6 ≤ weight[i] ≤ 10^6$). The next part of each test case describes the edges in the graph at the beginning. Vertexes are numbered from $1$ to $N$. The last part of each test case describes the operations to be performed on the graph. It is guaranteed that the number of query operations [Q X K] in each case will be in the range $[1, 2 * 10^5]$, and there will be no more than $2 * 10^5$ operations that change the values of the vertexes [C X V].

There will be a blank line between two successive cases. A case with $N = 0$, $M = 0$ indicates the end of the input file and this case should not be processed by your program.

Output

For each test case, output one real number – the average answer of all queries, in the format as indicated in the sample output. Please note that the result is rounded to six decimal places.

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
29
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

思路

  • 容易想到离线解决问题。先读入全部操作得到最后的图,然后逆序执行操作。这样删除就变成了合并。
  • 对于每一个联通分量,我们用一个Splay来维护其中的点权,这样查询第$k$大是没问题的。
  • 对于合并操作,我们就要将两个Splay合并。树合并的时候,我们如果采用启发式合并,将小的往大的合并,任意结点被移动到新树中时,该结点所在树的大小至少加倍。因此任意结点至多被移动$\log_2n$次。总的时间复杂度为$O(n\log^2n)$
  • 注意处理$k$不合法的情况,不然会在Splay的kth中死循环。
  • 写了好久TAT

代码

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
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

const int maxn = 1 << 15;
#define key_value ch[ch[root][1]][0]

struct Splay
{
int sz[maxn], ch[maxn][2], key[maxn], fa[maxn];
int root, tot;
int stk[maxn], top;

#ifndef ONLINE_JUDGE
void Treavel(int x)
{
if (x)
{
Treavel(ch[x][0]);
printf("结点:%2d: 左儿子 %2d 右儿子 %2d 父结点 %2d size= %2d key= %2d\n", x, ch[x][0], ch[x][1], fa[x], sz[x], key[x]);
Treavel(ch[x][1]);
}
}

void debug()
{
printf("root:%d\n", root);
Treavel(root);
}
#endif

int newnode(int p = 0, int k = 0)
{
int x = top ? stk[top--] : ++tot;
fa[x] = p;
sz[x] = 1;
ch[x][0] = ch[x][1] = 0;
key[x] = k;
return x;
}

inline void init() { tot = top = 0; }

inline void pushup(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1; }

void rotate(int x, int d)
{
int y = fa[x];
ch[y][d ^ 1] = ch[x][d];
fa[ch[x][d]] = y;
if (fa[y]) ch[fa[y]][ch[fa[y]][1] == y] = x;
fa[x] = fa[y];
ch[x][d] = y;
fa[y] = x;
pushup(y);
}

void splay(int x, int goal = 0)
{
while (fa[x] != goal)
{
if (fa[fa[x]] == goal)
rotate(x, ch[fa[x]][0] == x);
else
{
int y = fa[x];
int d = ch[fa[y]][0] == y;
ch[y][d] == x ? rotate(x, d ^ 1) : rotate(y, d);
rotate(x, d);
}
}
pushup(x);
if (goal == 0) root = x;
}

int kth(int r, int k)
{
int t = sz[ch[r][0]] + 1;
if (t == k) return r;
return t > k ? kth(ch[r][0], k) : kth(ch[r][1], k - t);
}

void insert(int v)
{
if (root == 0)
{
root = newnode(0, v);
return;
}
int p = root;
while (ch[p][key[p] < v]) p = ch[p][key[p] < v];
ch[p][key[p] < v] = newnode(p, v);
pushup(p);
splay(ch[p][key[p] < v]);
}

void erase(int x)
{
splay(x);
stk[++top] = x;
if (!ch[root][0] || !ch[root][1])
{
root = ch[root][0] + ch[root][1];
fa[root] = 0;
return;
}
int tmp = kth(ch[root][1], 1);
splay(tmp, root);
key_value = ch[root][0], root = ch[root][1], fa[ch[root][0]] = root, fa[root] = 0;
pushup(root);
}

int query(int x, int k)
{
splay(x);
if (k < 1 || k > sz[root]) return 0;
return key[kth(root, sz[root] - k + 1)];
}

void change(int x, int v) { erase(x), insert(v); }

int pa[maxn];
int find(int x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }

void dfs(int r)
{
if (!r) return;
dfs(ch[r][0]), dfs(ch[r][1]);
stk[++top] = r;
insert(key[r]);
}

void merge(int x, int y)
{
x = find(x), y = find(y);
if (x == y) return;
pa[y] = x;
splay(x), splay(y);
if (sz[x] > sz[y]) swap(x, y);
root = y;
dfs(x);
}

} gao;

const int maxc = 1 << 19;
struct Cmd
{
char op;
int x, p;
} cmd[maxc];

const int maxm = 1 << 16;
int w[maxn], from[maxm], to[maxm];
bool removed[maxm];
inline void add(const int& x) { gao.merge(from[x], to[x]); }

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int kase = 0;
int n, m;
while (~scanf("%d%d", &n, &m) && n + m)
{
gao.init();
for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
for (int i = 1; i <= m; i++) scanf("%d%d", &from[i], &to[i]);
clr(removed, 0);
int tot = 0, query_cnt = 0;
for (char op; ~scanf(" %c", &op) && op != 'E'; tot++)
{
static int x, p, v;
scanf("%d", &x);
if (op == 'D') removed[x] = true;
if (op == 'Q') scanf("%d", &p), ++query_cnt;
if (op == 'C')
{
scanf("%d", &v);
p = w[x], w[x] = v;
}
cmd[tot] = {op, x, p};
}

if (!query_cnt)
{
printf("Case %d: 0.000000\n", ++kase);
continue;
}

for (int i = 1; i <= n; i++) gao.newnode(0, w[i]), gao.pa[i] = i;
for (int i = 1; i <= m; i++)
if (!removed[i]) add(i);

ll query_tot = 0;
for (int i = tot - 1; ~i; i--)
{
if (cmd[i].op == 'D') add(cmd[i].x);
if (cmd[i].op == 'Q') query_tot += gao.query(cmd[i].x, cmd[i].p);
if (cmd[i].op == 'C') gao.change(cmd[i].x, cmd[i].p);
}
printf("Case %d: %.6lf\n", ++kase, query_tot * 1.0 / query_cnt);
}
return 0;
}
捐助作者
0%