题目描述
译自 COCI 2020/2021 Contest #3 T5. Specijacija
给定一个长度为 n 的正整数序列 a1…n ,满足 2i(i−1)<ai≤2i(i+1) 。
通过这一个序列构造一个有 2(n+1)(n+2) 个节点的二叉树。该二叉树有 n+1 层,第 i 层有 i 个节点。
第 i 层包含编号为 2i(i−1)+1,…,2i(i+1) 的节点。节点 ai 有两个儿子,而同一层的其他节点则只有一个儿子。
比如,序列 {1,2,6} 所构造的树就是这样的。
有 q 组询问,给定 x,y ,你需要求出节点 x,y 的最近公共祖先。
输入格式
第一行包含三个整数 n,q,t ,分别表示序列的长度、询问次数和关于强制在线的参数。
第二行有 n 个正整数,第 i 个数为 ai 。
接下来的 q 行中每一行有两个正整数 xi~,yi~ ,即询问的参数 xi,yi 加密后的结果。
其中:
xi=((x~i−1+t⋅zi−1)mod2(n+1)(n+2))+1yi=((y~i−1+t⋅zi−1)mod2(n+1)(n+2))+1
zi 为第 i 组询问的答案,如果 i=0 ,则置 zi 为 0 。
注意到当 t=0 时 xi=xi~ 而 yi=yi~ 。
输出格式
输出共 q 行,其中第 i 行一个正整数,表示 xi,yi 的最近公共祖先。
样例 1
3 5 0
1 2 6
7 10
8 5
6 2
9 10
2 3
1
5
1
6
1
3 5 1
1 2 6
7 10
8 5
6 2
9 10
2 3
1
6
2
1
1
两个样例所表示的树就是上图所描述的树。
第二个样例中真实的 x,y 列举如下:
- x1=7,y1=10
- x2=9,y2=6
- x3=2,y3=8
- x4=1,y4=2
- x5=3,y5=4
数据范围与提示
对于所有子任务,保证 1≤n,q≤2×105,t∈{0,1} 。
详细子任务附加限制与分值如下表:
子任务 |
附加限制 |
分值 |
1 |
q=1,t=0 |
10/110 |
2 |
n≤1000,t=0 |
10/110 |
3 |
t=0 |
30/110 |
4 |
t=1 |
60/110 |