P3273 [SCOI2011] Tricky Operations

There are $N$ nodes labeled from $1$ to $N$, initially all disconnected. The initial weight of the $i$-th node is $a_i$. Then the following operations occur: - `U x y`: add an edge connecting node $x$ and node $y$. - `A1 x v`: increase the weight of node $x$ by $v$. - `A2 x v`: increase the weights of all nodes in the connected component containing node $x$ by $v$. - `A3 v`: increase the weights of all nodes by $v$. - `F1 x`: output the current weight of node $x$. - `F2 x`: output the maximum weight within the connected component containing node $x$. - `F3`: output the maximum weight among all nodes.

The first line contains an integer $N$, the number of nodes. The second line contains $N$ integers $a_1,a_2,\dots,a_N$, the initial weights of the $N$ nodes. The next line contains an integer $Q$, the number of subsequent operations. Each of the following $Q$ lines is in one of the formats described above.

For operations `F1 x`, `F2 x`, and `F3`, output the corresponding result, one per line.

Constraints: - For $30\%$ of the testdata, $N \le 100$, $Q \le 10000$. - For $80\%$ of the testdata, $N \le 100000$, $Q \le 100000$. - For $100\%$ of the testdata, $N \le 300000$, $Q \le 300000$. - For all testdata, the input is guaranteed to be valid, and $-1000 \le v, a_1, a_2, \dots, a_N \le 1000$. Translated by ChatGPT 5