P7172 [COCI 2020/2021 #3] Specijacija

Given a positive integer $n$ and a sequence of positive integers $a_1, a_2, \cdots, a_n$ satisfying $\frac{i(i-1)}{2} \lt a_i \le \frac{i(i+1)}{2}$. This sequence parameterizes a tree with $\frac{(n+1)(n+2)}{2}$ nodes. The tree has $n+1$ levels, where level $1,2,\cdots,n+1$ contains $1,2,\cdots,n+1$ nodes respectively, as shown in the figure:  It is parameterized by $a=(1,2,6)$. Level $i$ contains nodes $\frac{i(i-1)}{2}+1, \cdots, \frac{i(i+1)}{2}$. Node $a_i$ has two children, while all other nodes on the same level have only one child. In each level, children are assigned to nodes in increasing order of node indices, always choosing the smallest-index node in the next level that has not been assigned yet. Answer $q$ queries. For each query, find the lowest common ancestor of $x$ and $y$, i.e., the node with the largest index that is an ancestor of both $x$ and $y$.

The first line contains three integers $n, q, t$, representing the number of parameters, the number of queries, and the parameter used to determine node indices. The second line contains a sequence $a$ of length $n$ (for each $a_i$, $\frac{i(i-1)}{2} \lt a_i \le \frac{i(i+1)}{2}$). Each of the next $q$ lines contains two integers $\tilde x_i$ and $\tilde y_i$ ($1 \le \tilde x_i, \tilde y_i \le \frac{(n+1)(n+2)}{2}$), used to determine the node indices involved in the $i$-th query. Let $z_i$ be the answer to the $i$-th query, and define $z_0=0$. The node indices involved in the $i$-th query are: $$x_i=[(\tilde x_i-1+t \times z_{i-1}) \bmod \frac{(n+1)(n+2)}{2}]+1$$ $$y_i=[(\tilde y_i-1+t \times z_{i-1}) \bmod \frac{(n+1)(n+2)}{2}]+1$$ Note: When $t=0$, we have $x_i=\tilde x_i$ and $y_i=\tilde y_i$. When $t=1$, the node indices involved in the query should be determined using previous answers.

Output $q$ lines in total. On the $i$-th line, output the lowest common ancestor of $x_i$ and $y_i$.

**[Sample Explanation #1 / #2]** The shapes of the trees represented by the two samples are already shown in the figure in the problem description. In the second sample, the node indices involved in each query are: $x_1=7$, $y_1=10$; $x_2=9$, $y_2=6$; $x_3=2$, $y_3=8$; $x_4=1$, $y_4=2$; $x_5=3$, $y_5=4$. **[Constraints]** | Subtask | Points | Constraints and Notes | | :----------: | :----------: | :----------: | | $1$ | $10$ | $q=1, t=0$ | | $2$ | $10$ | $n \le 1000, t=0$ | | $3$ | $30$ | $t=0$ | | $4$ | $60$ | $t=1$ | For $100\%$ of the testdata, $1 \le n,q \le 2 \times 10^5$, and $t \in \{0,1\}$. **[Notes]** **The scoring for this problem follows the original COCI problem, with a full score of $110$.** **Translated from [COCI2020-2021](https://hsin.hr/coci/) [CONTEST #4](https://hsin.hr/coci/archive/2020_2021/contest3_tasks.pdf) _T5 Specijacija_.** Translated by ChatGPT 5