CF2261G.1 2 3 and XOR, Where Did Everybody Go?
省选/NOI-
通过率:0%
时间限制:7.00s
内存限制:1024MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given a sequence a consisting of n non-negative integers.
Given a sequence b consisting of k non-negative integers, define a dot increment on b as the following operation:
- Select an index i (1≤i≤k), and add any non-negative integer of choice to bi.
Then, let f(b) be the minimum value of b1⊕b2⊕…⊕bk after performing a dot increment on b exactly once.∗
Please find the value of the following sum.
∑1≤l≤r≤nf([al,al+1,…,ar])
∗Here, ⊕ denotes the bitwise XOR operation.
给你一个由 n 个非负整数组成的序列 a。
给定一个由 k 个非负整数组成的序列 b,定义对 b 的**点增操作(dot increment)**为如下操作:
- 选择一个下标 i(1≤i≤k),并将任意选定的非负整数加到 bi 上。
然后,记 f(b) 为对 b 恰好执行一次点增操作后,所能得到的 b1⊕b2⊕…⊕bk 的最小值。∗
请计算以下和式的值:
∑1≤l≤r≤nf([al,al+1,…,ar])
∗此处 ⊕ 表示按位异或运算(bitwise XOR)。
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤104). The description of the test cases follows.
The first line of each test case contains an integer n (1≤n≤4⋅105).
The second line of each test case contains integers a1,a2,…,an (0≤ai<225).
It is guaranteed that the sum of n does not exceed 4⋅105 over all test cases.
每个测试包含多个测试用例。第一行包含测试用例的数量 t(1≤t≤104)。随后是各测试用例的描述。
每个测试用例的第一行包含一个整数 n(1≤n≤4⋅105)。
每个测试用例的第二行包含整数 a1,a2,…,an(0≤ai<225)。
保证所有测试用例中 n 的总和不超过 4⋅105。
输出格式
For each test case, output the answer to the problem on a separate line.
对于每个测试用例,在单独的一行上输出该问题的答案。
输入输出样例
输入#1
4 5 5 4 6 7 5 5 3 3 2 2 3 1 67 10 1827481 5921082 14619611 643973 6718274 2948 244716 29 0 6717827
输出#1
43 21 67 36695941
说明/提示
In the first test case, for example, consider f([5,4,6,7,5])
By incrementing b2=4 by 1, b becomes [5,5,6,7,5], and 5⊕5⊕6⊕7⊕5=4.
It can be shown that b1⊕b2⊕b3⊕b4⊕b5 cannot be smaller than 4 after one dot increment.
The sum of minimum values over all subarrays can be shown to be 43.
在第一个测试用例中,例如,考虑 f([5,4,6,7,5])。
通过将 b2=4 增加 1,b 变为 [5,5,6,7,5],此时 5⊕5⊕6⊕7⊕5=4。
可以证明:经过一次点增量操作后,b1⊕b2⊕b3⊕b4⊕b5 的值不可能小于 4。
所有子数组的最小值之和可证为 43。
输入解题思路,AI测评打分。不知道怎么写?