#PQJ1548x13409. QOJ 1548_13409

    ID: 2647 传统题 4000ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2021 集训树上算法

QOJ 1548_13409

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