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