CF1054D Changing Array

课间时，Vanya 走进教室，看到黑板上写着一个长度为 $n$ 的 $k$ 位整数数组 $a_1, a_2, \ldots, a_n$。一个整数 $x$ 被称为 $k$ 位整数，当且仅当 $0 \leq x \leq 2^k - 1$。 当然，Vanya 忍不住开始修改黑板上的数字。为了不被人发现，Vanya 只允许自己进行一种操作：选择数组的某个下标 $i$（$1 \leq i \leq n$），并将 $a_i$ 替换为 $\overline{a_i}$。我们定义 $k$ 位整数 $x$ 的 $\overline{x}$ 为所有 $k$ 位都与 $x$ 对应位相反的 $k$ 位整数。 Vanya 不喜欢数字 $0$。因此，他喜欢这样的区间 $[l, r]$（$1 \leq l \leq r \leq n$），使得 $a_l \oplus a_{l+1} \oplus \ldots \oplus a_r \neq 0$，其中 $\oplus$ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。请你求出，经过若干次（可以为 $0$ 次）上述操作后，Vanya 最多能得到多少个他喜欢的区间。

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 200\,000$，$1 \leq k \leq 30$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq 2^k - 1$），表示 $k$ 位整数数组。

输出一个整数，表示通过若干次操作后，Vanya 最多能得到多少个异或和不为 $0$ 的区间。

在第一个样例中，如果 Vanya 不进行任何操作，得到的数组有 $5$ 个他喜欢的区间。如果他对 $i=2$ 进行操作，得到数组 $[1, 0, 0]$，因为当 $k=2$ 时，$\overline{3}=0$。这个数组有 $3$ 个他喜欢的区间。同样地，如果对 $i=3$ 和 $i=2$ 各进行一次操作，可以得到数组 $[1, 0, 3]$，这样也有 $5$ 个他喜欢的区间。可以证明，他无法得到 $6$ 个或更多他喜欢的区间。 在第二个样例中，为了得到 $19$ 个他喜欢的区间，可以对 $i=3$、$i=4$、$i=5$、$i=6$ 进行操作，得到数组 $[1, 4, 3, 0, 4, 3]$。 由 ChatGPT 4.1 翻译