305556: CF1054D. Changing Array
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Changing Array
题意翻译
给你一个序列$a$,$0 ≤ $ $ a_{i}$ $≤$ $2^{k}-1$,你可以修改里面的任意元素任意次,修改方法为把序列里的一个数$ai⊕$ $2^{k}-1$ 其中$⊕$为异或运算,求最多可以构成多少个连续区间$[l,r]$使得$a_{l} ⊕a_{l+1}$ $⊕ ... $ $a_{r-1} ⊕ ar≠0 $题目描述
At a break Vanya came to the class and saw an array of $ n $ $ k $ -bit integers $ a_1, a_2, \ldots, a_n $ on the board. An integer $ x $ is called a $ k $ -bit integer if $ 0 \leq x \leq 2^k - 1 $ . Of course, Vanya was not able to resist and started changing the numbers written on the board. To ensure that no one will note anything, Vanya allowed himself to make only one type of changes: choose an index of the array $ i $ ( $ 1 \leq i \leq n $ ) and replace the number $ a_i $ with the number $ \overline{a_i} $ . We define $ \overline{x} $ for a $ k $ -bit integer $ x $ as the $ k $ -bit integer such that all its $ k $ bits differ from the corresponding bits of $ x $ . Vanya does not like the number $ 0 $ . Therefore, he likes such segments $ [l, r] $ ( $ 1 \leq l \leq r \leq n $ ) such that $ a_l \oplus a_{l+1} \oplus \ldots \oplus a_r \neq 0 $ , where $ \oplus $ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). Determine the maximum number of segments he likes Vanya can get applying zero or more operations described above.输入输出格式
输入格式
The first line of the input contains two integers $ n $ and $ k $ ( $ 1 \leq n \leq 200\,000 $ , $ 1 \leq k \leq 30 $ ). The next line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \leq a_i \leq 2^k - 1 $ ), separated by spaces — the array of $ k $ -bit integers.
输出格式
Print one integer — the maximum possible number of segments with XOR not equal to $ 0 $ that can be obtained by making several (possibly $ 0 $ ) operations described in the statement.
输入输出样例
输入样例 #1
3 2
1 3 0
输出样例 #1
5
输入样例 #2
6 3
1 4 4 7 3 4
输出样例 #2
19