[COCI2020-2021#3] Specijacija

题目描述

给定一个正整数 $n$ 个一个满足 $\frac{i(i-1)}{2} \lt a_i \le \frac{i(i+1)}{2}$ 的正整数序列 $a_1, a_2, \cdots, a_n$。 该序列是一棵包含 $\frac{(n+1)(n+2)}{2}$ 个节点的树参数化而来的,它包括 $n+1$ 层,每层分别包括 $1, 2, \cdots, n+1$ 个节点,如图所示: ![](https://cdn.luogu.com.cn/upload/image_hosting/bvug13ny.png) 它由 $a=(1,2,6)$ 参数化而来。 第 $i$ 层包含节点 $\frac{i(i-1)}{2}+1, \cdots, \frac{i(i+1)}{2}$。节点 $a_i$ 有两个孩子,而其他同层的节点都只有一个孩子。 请回答 $q$ 个询问,求 $x,y$ 的最大公共祖先,即既是 $x$ 的祖先,又是 $y$ 的祖先且权值最大的节点。

输入输出格式

输入格式


第一行包含三个整数 $n,q,t$,分别表示参数的数量、询问次数和用来决定节点权值的参数。 第二行输入一个长度为 $n$ 的序列 $a$(其中对于每一个数 $a_i$ 有 $\frac{i(i-1)}{2} \lt a_i \le \frac{i(i+1)}{2}$)。 接下来的 $q$ 行中的第 $i$ 行包含两个整数 $\tilde x_i$ 和 $\tilde y_i$($1 \le \tilde x_i, \tilde y_i \le \frac{(n+1)(n+2)}{2}$),用来决定询问时节点的权值。 设 $z_i$ 为第 $i$ 次询问的结果,规定 $z_0=0$。第 $i$ 次询问的权值为: $$x_i=[(\tilde x_i-1+t \times z_{i-1}) \bmod \frac{(n+1)(n+2)}{2}]+1$$ $$x_i=[(\tilde y_i-1+t \times z_{i-1}) \bmod \frac{(n+1)(n+2)}{2}]+1$$ 注:当参数 $t=0$ 时,满足 $x_i=\tilde x_i$,$y_i=\tilde y_i$。当 $t=1$ 时,权值应通过先前的答案来决定。

输出格式


输出共 $q$ 行,其中第 $i$ 行,输出 $x_i$ 和 $y_i$ 的最大公共祖先。

输入输出样例

输入样例 #1

3 5 0
1 2 6
7 10
8 5
6 2
9 10
2 3

输出样例 #1

1
5
1
6
1

输入样例 #2

3 5 1
1 2 6
7 10
8 5
6 2
9 10
2 3

输出样例 #2

1
6
2
1
1

说明

**【样例解释 #1 / #2】** 两个样例所表示的树的形状在题目描述的图中已经呈现。 第二个样例中各个节点的权值: $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$。 **【数据范围】** | Subtask | 分值 | 数据范围及约定 | | :----------: | :----------: | :----------: | | $1$ | $10$ | $q=1, t=0$ | | $2$ | $10$ | $n \le 1000, t=0$ | | $3$ | $30$ | $t=0$ | | $4$ | $60$ | $t=1$ | 对于 $100\%$ 的数据,$1 \le n,q \le 2 \times 10^5$,$t \in \{0,1\}$。 **【说明】** **本题分值按 COCI 原题设置,满分 $110$。** **题目译自 [COCI2020-2021](https://hsin.hr/coci/) [CONTEST #4](https://hsin.hr/coci/contest3_tasks.pdf) _T5 Specijacija_。**