P12014 [Ynoi April Fool's Round 2025] Jail Hat.

    

Hoshino Kana gives you an undirected graph with $n$ vertices. The graph initially has no edges. She also gives you integers $u, v$ and $a_1, a_2, \cdots, a_n$. There are $q$ operations of four types: 1. ```1 x y```: Add an edge between $x$ and $y$. It is guaranteed that this edge does not exist before. 2. ```2 x y```: Delete the edge between $x$ and $y$. It is guaranteed that this edge exists before. 3. ```3 x y```: Modify $a_x$ to $y$. 4. ```4 x```: Suppose the graph is divided into $k$ connected components $C_1, C_2, \cdots, C_k$. Compute $\sum_{i=1}^k \prod_{j\in C_i}(a_j+x) \bmod u^v$.

The first line contains four integers $n, q, u, v$. The second line contains $n$ integers $a_1, a_2, \cdots, a_n$. The next $q$ lines each describe one operation.

Output several lines. Each line contains one integer, the answer for each type $4$ operation.

Idea: I forgot the source. Please ask the original problem setter by private message on QQ. ### Sample 2 See the attachments `ex_c2.in` and `ex_c2.ans`. This sample satisfies Subtask $1$. ### Sample 3 See the attachments `ex_c3.in` and `ex_c3.ans`. This sample satisfies Subtask $2$. ### Sample 4 See the attachments `ex_c4.in` and `ex_c4.ans`. This sample satisfies Subtask $6$. ### Limits and Notes This problem uses bundled tests. For $100\%$ of the data, $1\leq n,q\leq 10^5$, $1\leq u\leq 10$, $1\leq v\leq 4$, $0\leq a_i < 10^4$. In type $3$ operations, $y$, and in type $4$ operations, $x$, are both non-negative integers less than $10^4$. | Subtask ID | Score | $n\leq$ | $q\leq$ | Special Property | | :--------- | ---- | ------- | ------- | ---------------------------------------- | | $1$ | $20$ | $5000$ | $5000$ | $/$ | | $2$ | $10$ | $10^5$ | $10^5$ | For all type $4$ operations, $x=0$. | | $3$ | $15$ | $10^5$ | $10^5$ | $v=1$. | | $4$ | $15$ | $10^5$ | $10^5$ | For all type $4$ operations, $x$ is a multiple of $u$. | | $5$ | $15$ | $10^5$ | $10^5$ | There are no type $2$ or type $3$ operations. | | $6$ | $25$ | $10^5$ | $10^5$ | $/$ | Translated by ChatGPT 5