#P12559. [UOI 2024] Zeroing the segment

    ID: 14125 远端评测题 6000ms 512MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>2024交互题Special JudgeUOI(乌克兰)

[UOI 2024] Zeroing the segment

题目描述

This is a problem with graders.

For an array of positive integers bb of length mm, we define f(b)f(b) as follows:

  • Let initially a variable xx be equal to 00;
  • For one coin, it is allowed to increase the value of xx by 11;
  • For one coin, it is allowed to choose an element of the array bib_i (1im1\le i\le m) and replace it with (bix)(b_i \oplus x), where \oplus denotes the operation of bitwise exclusive OR;
  • f(b)f(b) equals the minimum number of coins needed to make all elements of the array bb simultaneously equal to zero.

The bitwise exclusive OR of non-negative integers aa and bb (ab)(a \oplus b) equals a non-negative integer, in which in the binary representation, there is a one at a certain position only if in the binary representations of aa and bb at this position there are different values. For example, $3_{10} \oplus 5_{10} = 0011_{2} \oplus 0101_{2} = 0110_{2} = 6_{10}$.

An array of positive integers aa of length nn and qq queries of the form ll, rr are given. For each query, it is necessary to find f([al,al+1,,ar])f([a_l,a_{l+1},\ldots,a_r]).

You need to implement the following functions:

void init(integer n, array of integers a)
  • nn --- an integer representing the length of the array;
  • aa --- an array of integers of length nn;
  • this function does not return anything.
integer ask(integer l, integer r)
  • ll --- an integer representing the left boundary of the query;
  • rr --- an integer representing the right boundary of the query;
  • this function returns an integer --- f([al,al+1,,ar])f([a_l,a_{l+1},\ldots,a_r]).
array of integers askAll(integer q, array of integers l, array of integers r)
  • qq --- an integer representing the number of queries;
  • ll --- an array of integers of length qq; lil_i represents the left boundary of the ii-th query;
  • rr --- an array of integers of length qq; rir_i represents the right boundary of the ii-th query;
  • this function returns an array of integers; the ii-th number should be equal to the answer to the ii-th query.

输入格式

The first line contains three integers nn, qq, and tt (1n,q21051 \leq n, q \leq 2 \cdot 10^5; 1t21 \leq t \leq 2) --- the number of numbers, the number of queries, and the format of the queries, respectively.

The second line contains nn integers a1,a2,,ana_1, a_2, \dots, a_n (1ai<2601 \leq a_i < 2^{60}) --- the elements of the array aa.

The next qq lines contain two integers ll and rr (1lrn1 \leq l \leq r \leq n) --- the parameters of the ii-th query.

The function init\tt{init} will be called exactly once.

If t=1t=1, then the function askAll\tt{askAll} with all queries will be called exactly once. If t=2t=2, then the function ask\tt{ask} will be called exactly qq times.

输出格式

The grader will output qq integers in separate lines --- the answers to the queries.

7 6 1
5 4 3 5 7 7 7
1 4
4 7
3 7
1 7
2 6
1 1
9
11
12
14
12
6
7 6 2
5 4 3 5 7 7 7
1 4
4 7
3 7
1 7
2 6
1 1
9
11
12
14
12
6

提示

Scoring

  • (33 points): t=1t=1, ai=a1a_i=a_1 for 1in1\le i\le n;
  • (88 points): t=1t=1, aiaja_i \neq a_j for iji \neq j;
  • (33 points): t=1t=1, 2m+nai<2m+12^m+n \le a_i<2^{m+1} for some natural mm;
  • (99 points): t=1t=1, aiai+1a_i \le a_{i+1} for 1i<n1 \le i < n;
  • (1010 points): t=1t=1, n,q1000n, q \le 1000;
  • (1111 points): t=1t=1, li=1l_i=1 and ri=ir_i=i for 1iq1\le i\le q.
  • (1010 points): t=1t=1, n,q50000n, q \le 50000;
  • (2525 points): t=1t=1;
  • (99 points): t=2t=2, n,q105n, q \le 10^5;
  • (1212 points): t=2t=2.