不定期更新
Q.
\(n\) 个区间 \(\left [ l,r\right ]\)，给每个区间分组，使每个组内的区间两两不交，求最小的组数。
A.
结论：组数 \(k\) 是合法的，当且仅当不存在一个点被所有区间覆盖 \(> k\) 次。
证明：定义两个区间的偏序关系，\(b < c\) 则 \(\left [ a,b\right ]< \left [c,d\right]\)。那么问题等价于最小链覆盖，根据 Dliworth定理最小链覆盖等于最长反链。在反链中的任意两点不存在偏序关系，所以反链中的所有区间交集不为空，因为不存在一个点被覆盖 \(k\) 次，所以最长反链 \(\le k\)，即最小链覆盖 \(\le k\)。
通过这个结论，我们只需一个支持区间加，全局最大值的数据结构即可。
Q.
给定一个序列 \(a\)，支持两种操作：
- \(\forall i \in \left[l,r\right],a_i = a_i \oplus x\)
- 求 \(\max \limits_{i=l}^{r} a_i\)
A.
因为有异或求最大值，不难想到 01trie，这个东西树套树是维护不了的，于是想到分块套 trie。
具体来说，对于每个块都开一颗 trie。在修改整块时可以直接打上 \(tag\)，表示这个块被异或的值，在查询时直接查这个块中与 \(tag\) 异或值最大的即可。而散块可以将这个块的 trie 暴力重构，散块查询暴力即可，时间复杂度 \(O(n \sqrt n \log V)\)。
卡常技巧：重构可以在查询的时候再执行。
