#2164. Specijacija
Specijacija
Specijacija
题目描述
Croatian Open Competition in Informatics Task Specijacija Round 2, December 12th 2020 4 seconds / 1 GiB / 110 points Task Specijacija You are given a positive integer n and a sequence a1, a2, . . . , an of positive integers, such that i(i−1) < 2 ai ≤i(i+1) . 2 The sequence parameterizes a tree with (n+1)(n+2) vertices, consisting of n + 1 levels with 1, 2, . . . , n + 1 2 vertices, in the following way: 1 2 3 4 5 6 7 8 9 10 The tree parameterized by a = (1, 2, 6). The i-th level contains vertices i(i−1)
- 1, . . . , i(i+1) . The vertex ai has two children, and the rest of the 2 2 vertices on the level have one child each. We want to answer q queries of the form “what is the largest common ancestor of x and y”, i.e. the vertex with the largest label which is an ancestor of both x and y. Input The first line contains integers n, q and t (1 ≤n, q ≤200 000, t ∈{0, 1}), the number of parameters, the number of queries, and a value which will be used to determine the labels of vertices in the queries. The second line contains a sequence of n integers ai ( i(i−1) < ai ≤i(i+1) ) which parameterize the tree. 2 2 The i-th of the following q lines contains two integers exi and eyi (1 ≤exi, eyi ≤(n+1)(n+2) ) which will be 2 used to determine the labels of vertices in the queries. Let zi be the answer to the i-th query, and let z0 = 0. The labels in the i-th query xi and yi are: (exi −1 + t · zi−1) mod (n+1)(n+2) xi =
- 1, 2 (eyi −1 + t · zi−1) mod (n+1)(n+2) yi =
- 1, 2 where mod is the remainder of integer divison. Remark: Note that if t = 0, it holds xi = exi and yi = eyi, so all queries are known from input. If t = 1, the queries are not known in advance, but are determined using answers to previous queries. Output Output q lines. In the i-th line, output the largest common ancestor of xi and yi. 6 of 7 Croatian Open Competition in Informatics Task Specijacija Round 2, December 12th 2020 4 seconds / 1 GiB / 110 points Scoring Subtask Points Constraints q = 1, t = 0 1 10 n ≤1000, t = 0 2 10 t = 0 3 30 4 60 t = 1 Examples input input 3 5 0 3 5 1 1 2 6 1 2 6 7 10 7 10 8 5 8 5 6 2 6 2 9 10 9 10 2 3 2 3 output output 1 1 5 6 1 2 6 1 1 1 Clarification of the examples: The tree from both examples is shown on the figure in the statement. Labels of verticies in queries in the second example are: x1 = 7, y1 = 10, x2 = 9, y2 = 6, x3 = 2, y3 = 8, x4 = 1, y4 = 2, x5 = 3, y5 = 4. 7 of 7
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3 5 0
1 2 6
7 10
8 5
6 2
9 10
2 3
1
5
1
6
1
样例 2
3 5 1
1 2 6
7 10
8 5
6 2
9 10
2 3
1
6
2
1
1