## 分段
#位运算 #状压dp #前缀和
首先看到一段区间的异或和就可以想到前缀和，先令 $p_i=\oplus_{j=1}^i a_j$，于是我们的要求就变成了对于每一个 $i$ 求出 $\max\limits_{j=0}^i p_j+(p_j\oplus p_i)$。
- [I] 容易想到亦或是不进位的加法，而通过与运算可以得到所有要进位的位，因此有恒等式 $A+B=(A\oplus B)+2\times(A\operatorname{\&}B)$，变形得到 $A\oplus B=A+B-2\times(A\operatorname{\&}B)$。
应用到原式得到 $p_j+(p_j\oplus p_i)=p_j+p_i+p_j-2(p_i\operatorname{\&}p_j)$，即 $p_i+2\times (p_j-p_i\operatorname{\&}p_j)$。而 $p_j-p_i\operatorname{\&}p_j$ 实际上是 $p_j$ 减去所有 $p_i$ 和 $p_j$ 共有的 $1$ 的位，当 $p_j$ 此位为 $0$ 或者 $p_i,p_j$ 均为 $1$ 时答案为 $0$，否则为 $1$，发现和 $p_j\operatorname{\&}\sim p_i$ 的逻辑一样（$\sim$ 是取反）。
- [p] 所以我们的任务就变成了对于每一个 $p_i$，找一个 $p_j$ $(j<i)$ 使得 $p_i+2(p_j\operatorname{\&}\sim p_i)$ 最大，答案就是这个表达式的值。
于是我就理所应当地想到了 01 字典树，毕竟涉及到位运算。对于我们需要配对的 $p_i$，贪心地从高到低枚举每一位，如果 $p_i$ 这一位是 $1$，那么优先走 $1$ 的那边，否则走 $0$ 的那边。但是如果 $p_i$ 这一位是 $0$ 的话，问题就来了，$1$ 和 $0$ 的两边都能走，如果都走的话那么时间复杂度就会爆炸。
具体来说，如果 $p_i$ 当中有 $x$ 个 $0$，那么单次查询最坏时间复杂度将会飙到 $\mathcal O(2^{x}\log_2 n)$。当然，这里 $x$ 的期望是 ${} \cfrac{\log_2 V}{2} {}$ 的，由于值域与 $n$ 同阶（其实是分不清楚），单次查询期望时间复杂度是 $\mathcal O(\sqrt{n}\log_2 n)$ 的，当然可能会被极端数据卡掉。
不过我想到了一个妙招，就是把所有数取反了之后做按位并，答案再取反和直接做按位与是一样的，因此对于 $0$ 多的就做按位并，$1$ 多的就做按位与，这样子最坏时间复杂度就控制到了 $\mathcal O(n\sqrt n\log_2 n)$，但变化不大。
- [c] 我就写的这个，挂 $35$ 分。
其实我们离正解很近了。对于一个 $0$ 位，字典树当中需要往两边递归导致复杂度爆炸，但是实际上我们并不需要实际递归下去。回到原式问题之中：
- [?] 我们为什么要用 01 字典树？
- [!] 因为它可以记录之前所有位的前缀。
也就是对于一个数，它必须在我们查询的前缀中才能被选中（也就是前缀是 $1$ 的地方这个数也必须是 $1$，而 $0$ 的地方任意）。这很像什么？前缀必须是我们选择的数的子集，所以我们会想到什么？子集 DP！
但是子集 DP 是离线的，如果非要在线处理需要枚举新加入的数的所有子集，这当然会超时，我们也不需要这种方式。可以把下标存进去，DP 的时候取 $\min$ 用来最后判断是否在要求的前缀 $[0,i]$ 中。
设 $dp_i$ 表示所有包含 $i$ 的超集中，最小的下标。收集型的转移就是枚举 $i$ 中未出现 $1$ 的位，然后对下标取最小值，即 $dp_i=\min\limits_{j\not\in i}(dp_{i\operatorname{|}j})$。这个预处理的时间复杂度是 $\mathcal O(n\log_2 n)$ 的。
对于查询，我们还是从高到低贪心地枚举位，尝试将这一位变成 $1$，不过所选择的数必须包含已选的前缀（即当前的 $ans$）且被包含在前缀 $[0,i]$ 中。时间复杂度 $\mathcal O(n\log_2 n)$。
- [n] 这道题目思维性质还是很强的，最开始的前缀和转换很简单但是位运算的推导需要灵活应用恒等式。最难的部分就是查询了，很多人像我一样都想到了在线地添加元素并查询，而详细用法的数据结构就是 01 字典树了，但是对于按位与很难解决需要双边递归的问题。其实只需要注意到 01 字典树的本质——高位前缀，转变思路离线下来用子集 DP 模拟前缀被覆盖的过程，并记录下标以满足 $[0,i]$ 的前缀限制条件即可。
```cpp
#include <iostream>
using namespace std;
using LL = long long;
const LL kMaxN = 1e6 + 5, kLog = 22;
LL a[kMaxN], dp[1 << kLog], n, ans;
LL query(LL x, LL p) {
LL res = 0;
for (LL i = kLog - 1; i >= 0; i--) {
if (!(x & (1 << i)) && dp[res | (1 << i)] <= p) {
res |= 1 << i;
}
}
return x + 2 * res;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
fill(begin(dp), end(dp), 1e9);
for (LL i = 1; i <= n; i++) {
cin >> a[i];
a[i] ^= a[i - 1];
dp[a[i]] = min(dp[a[i]], i);
}
dp[0] = 0;
for (LL i = (1 << kLog) - 1; i >= 0; i--) {
for (LL j = 0; j < kLog; j++) {
if (!(i & (1 << j))) {
dp[i] = min(dp[i], dp[i | (1 << j)]);
}
}
}
for (LL i = 1; i <= n; i++) {
ans ^= i * query(a[i], i);
}
cout << ans << '\n';
return 0;
}
```
## 删除
我本来写了个简单的区间 DP，发现有些情况满足不了，所以就 WA $0$ 分了。
## 覆盖
啥也没写。
## 求和
啥也没写
## 总结
总分：$35+0+0+0=35$。
这次考试不咋行，全肝 T1 最后没写出来，其实我已经离正解很近了。虽然我一题也没有写出来，不过 T1 的思路确实让我受益匪浅，失败是成功之母，下次再加油。T1 总结在上面。