1902. 01trie上动态点分治

给定长为 n 的数组 a,下标从 1 计算。给定整数 k。记 \oplus 表示按位异或,\oplus_{1\le j\le i}a_j 表示 $a_1\oplus a_2\oplus\cdots\oplus ai。求: $ \max{k\le s\le n,s\le r\le n}\min{r-s+1\le i\le r}\oplus

未经优化的伪代码为:

ans = 0; for (int s = k; s <= n; ++s) { for (int r = s; r <= n; ++r) { min_v = 2e9; for (int i = r - s + 1; i <= r; ++i) { xsum = 0; for (int j = 1; j <= i; ++j) { xsum ^= a[j]; } min_v = min(min_v, xsum); } ans = max(ans, min_v); } }

输入

输入一行两个整数 n,k(2\le n\le 2\times10^6,2\le k\le n)

接下来输入一行 n 个整数,第 i 个整数代表 a_i(0\le a_i\le 10^9)

输出

输出一行一个整数,代表答案。

样例

标准输入 复制文本
8 2
0 1 1 2 6 5 2 7
标准输出 复制文本
3

来源

2022CS杯预选赛

登录以提交代码。
单点时限 2 秒
内存限制 256 MB
提交 23
通过 15