提示

T1

贪心 二分答案 二分查找

我们发现问题具有二分性，可以使用二分答案优化之前的做法解决这个问题。

T2

使用线段树解决，主要考察线段树的 pushup 操作。

可以发现当数字较多时可以考虑合并两块区间的答案：

• 拿左区间拥有的数字中靠右些的，右区间拿靠左的。
• 拿左区间的答案
• 拿右区间的答案

T3

$a_i \oplus a_{i+1} \oplus ... \oplus a_j \le \text{max}\{a_i,a_{i+1},...,a_{j}\}$

首先考虑简化的问题$\text{max}\{a_i,a_{i+1},...,a_{j}\}=k$为定值，那这个问题比较容易，对数组求异或前缀和 $s$，即求 $s_i\oplus s_j \le k$ 的 $(i,j),i,j\in[0,n],i\neq j$

建立01字典树，从0到n依次插入 $s_i$，每次插入前查找字典树内与 $s_i$ 异或值小于等于 $k$ 的元素个数。