#P12559. [UOI 2024] Zeroing the segment
[UOI 2024] Zeroing the segment
题目描述
This is a problem with graders.
For an array of positive integers of length , we define as follows:
- Let initially a variable be equal to ;
- For one coin, it is allowed to increase the value of by ;
- For one coin, it is allowed to choose an element of the array () and replace it with , where denotes the operation of bitwise exclusive OR;
- equals the minimum number of coins needed to make all elements of the array simultaneously equal to zero.
The bitwise exclusive OR of non-negative integers and 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 and 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 of length and queries of the form , are given. For each query, it is necessary to find .
You need to implement the following functions:
void init(integer n, array of integers a)
- --- an integer representing the length of the array;
- --- an array of integers of length ;
- this function does not return anything.
integer ask(integer l, integer r)
- --- an integer representing the left boundary of the query;
- --- an integer representing the right boundary of the query;
- this function returns an integer --- .
array of integers askAll(integer q, array of integers l, array of integers r)
- --- an integer representing the number of queries;
- --- an array of integers of length ; represents the left boundary of the -th query;
- --- an array of integers of length ; represents the right boundary of the -th query;
- this function returns an array of integers; the -th number should be equal to the answer to the -th query.
输入格式
The first line contains three integers , , and (; ) --- the number of numbers, the number of queries, and the format of the queries, respectively.
The second line contains integers () --- the elements of the array .
The next lines contain two integers and () --- the parameters of the -th query.
The function will be called exactly once.
If , then the function with all queries will be called exactly once. If , then the function will be called exactly times.
输出格式
The grader will output 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
- ( points): , for ;
- ( points): , for ;
- ( points): , for some natural ;
- ( points): , for ;
- ( points): , ;
- ( points): , and for .
- ( points): , ;
- ( points): ;
- ( points): , ;
- ( points): .