# 描述

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.

# 思路

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

0%