评价：我有异或症。
收集了一些跟异或相关的 trick，主要是以题目的形式放出来，做到了新的会再加。
由于本人不太会线性基，正在考虑要不要改成 01-Trie 学习笔记，相关题目暂时应该是没有，主要考虑异或本身的性质。
P4551 最长异或路径
设 \(dis_u\) 表示根到 \(u\) 路径上所有边权的异或和，众所周知异或有个很好的性质就是 \(a\oplus a=0\)，那么根据这点我们不难发现：\(u,v\) 路径上的边权异或和就等于 \(dis_u\oplus dis_v\)，因为 LCA 向上的边权都异或两次消去了。
现在的问题就变成：找出最大的一个点对 \((u,v)\)，使得 \(dis_u\oplus dis_v\) 最大。
将所有 \(dis_i\) 从高位到低位插入到 Trie 中，然后枚举 \(dis_u\)，贪心地从 Trie 上向下走找到最大的 \(dis_u\oplus dis_v\) 即可。具体来说就是每次看看能不能朝相反的那一位走，因为是从高位到低位插入这样一定是最优的。这个是非常基础的，相信大家都会。
时间复杂度 \(O(n\log V)\)。
P9745 树上异或
插播一个 dp 题。
朴素的想法是设 \(f_{u,i}\) 表示 \(u\) 所在的连通块权值为 \(i\) 时（只考虑子树内），子树内其他连通块的贡献之和，\(g_u\) 表示 \(u\) 所在子树的答案。
\(f_{u,i}\) 的转移就考虑每个儿子到自己的边断不断：
\[f_{u,i}\leftarrow f_{u,i}\times g_v+\sum_j f_{u,j}\times f_{v,i\oplus j} \]\(g_u\) 其实就求个和：
\[g_u=\sum_{x}x\times f_{u,x} \]时间复杂度 \(O(nV)\)，肯定过不去。
异或的一个很好的性质就是运算过程中每一位之间都是独立的，不妨按位考虑，也就是拆位。
设 \(f_{u,i,0/1}\) 表示 \(u\) 所在连通块权值的第 \(i\) 位为 \(0/1\) 时（同样也只考虑子树内），子树内其他连通块的贡献之和，\(g_u\) 表示 \(u\) 所在子树的答案。
转移其实大差不差：
\[\begin{aligned} f_{u,i,0}&\leftarrow f_{u,i,0}\times g_v+f_{u,i,0}\times f_{v,i,0}+f_{u,i,1}\times f_{v,i,1} \\ f_{u,i,1}&\leftarrow f_{u,i,1}\times g_v+f_{u,i,0}\times f_{v,i,1}+f_{i,i,1}\times f_{v,i,0} \end{aligned} \]哦，还有 \(g_u\) 改成这样：
\[g_{u}=\sum_{i}2^i\times f_{u,i,1} \]时间复杂度 \(O(n\log V)\)。
P5283 异或粽子
对 \(a_i\) 做一个异或前缀和，也就是记 \(s_i=\oplus_{j=1}^i a_i\)，那么区间 \([l,r]\) 的异或和就可以转化为 \(s_r\oplus s_{l-1}\)，特别规定 \(s_0=0\) 即可。
于是问题就转化成了：给你一个序列 \(s\)，求前 \(k\) 大的两两异或值之和。
注意这里要求 \(s_i\oplus s_j\) 时有 \(i<j\)，这是比较烦人的，但我们可以直接将 \(i<j\) 的限制去掉，转而求前 \(2k\) 大的两两异或值，然后再将答案除以 \(2\) 就好了，因为发现这样只是把 \(i,j\) 和 \(j,i\) 重复算了一遍（由于有 \(s_i\oplus s_i=0\)，\(i=j\) 的情况不需要任何特殊处理）。
事实上强制带 \(i<j\) 的限制也可以写可持久化 Trie 来解决。
考虑给定其中一个 \(s_i\) 时，能不能求出来第 \(k\) 大的 \(s_i\oplus s_j\)。其实是简单的，Trie 树上每个点维护子树内有几个数，把 \(s_i\) 扔到 Trie 上去进行一个类似于线段树上二分的过程就好了，当一位填 \(1\) 后最小排名不会超过 \(k\) 时就贪心填 \(1\)。
然后类比一下超级钢琴的做法，开一个小根堆，对于每个 \(s_i\) 先将最小的 \(s_i\oplus s_j\) 扔进堆里，这样就能保证堆顶一定是当前能取的最小值。接下来每次取出堆顶后，假如这个堆顶对它的 \(s_i\) 来说是第 \(t\) 小的，那就用上面方法把第 \(t+1\) 小的扔进去，这样重复 \(2k\) 次之后我们就成功求出前 \(2k\) 大的两两异或值了。
于是就做完了，时间复杂度 \(O((n+k)\log V)\)。
CF241B Friends
乍一看这不就是异或粽子吗？但是发现 \(k\) 非常大，而上面做法的复杂度是带个 \(k\) 的，过不去。
其实我们还有一个跟 \(k\) 无关的 \(O(n\log^2 V)\) 做法。
首先还是先把 \(k\) 乘上 \(2\)，这些就不多说了。然后我们分为两部分去完成：求出第 \(k\) 大的异或值 \(kth\)，求出大于等于 \(kth\) 的异或值之和。
对于第一部分，考虑二分答案 \(mid\)，判断 \(kth\) 是否小于等于 \(mid\)。不难发现此时我们只需要求出有多少对 \((i,j)\) 满足 \(a_i\oplus a_j>=mid\) 就行了，可以直接把每个 \(a_i\) 扔到 Trie 树上，类似线段树二分的过程（或者你也可以理解成枚举 LCP），如果遇到 \(mid\) 某位是 \(0\)，那么与 \(a_i\) 这位相反的那棵子树内的 \(a_j\) 就都是合法的，借此求出有多少个满足条件的 \(a_j\) 即可。这部分是两个 \(\log\) 的。
对于第二部分，考虑在 Trie 树上每个点 \(u\) 额外维护一个 \(f_{u,x}\) 表示经过 \(u\) 的 \(a_i\) 中有几个二进制下第 \(x\) 位是 \(1\)，这样把 \(a_i\) 扔到 Trie 树上走的过程中，如果遇到 \(kth\) 某位是 \(0\)，那么与 \(a_i\) 这位相反的那个子树内的数与 \(a_i\) 异或后就一定是大于 \(kth\) 的，相当于是求 \(a_i\) 异或其它经过这棵子树的 \(a_j\) 的和，贡献可以直接拆位算出来。
这样的话时空都是两个 \(\log\) 的，可以通过，但是空间其实可以去掉一个 \(\log\)。
考虑将 \(a_i\) 从小到大排序，有这么个性质：经过 Trie 上某个结点的 \(a_i\) 一定是一段连续的区间。
因此可以直接对原序列拆位做一个前缀和，需要统计某棵子树的贡献拆位时可以对应其在序列中的左右端点，差分计算贡献。
这样就是时间两个 \(\log\)，空间单 \(\log\) 了。
ABC252Ex K-th beautiful Necklace
很好的神仙题！技巧性很强的题，感觉就是各种 trick 的杂糅。
下文中令 \(m\) 为原题中的 \(c\)。发现这个 \(n\) 的范围是很神奇的，让人很容易去想暴力的可行性。当 \(m\) 确定时直接爆搜的上界显然是 \(O((\frac{n}{m})^m)\) 的，那么整体的上界具体到底是多少呢？事实上 \(m=3\) 时会取到 \(10^{11}\) 左右。
直接搜显然是爆炸了，但是注意到如果折半的话那搜一半的复杂度就会开个根号，只有 \(10^5\) 的级别（上界其实是 \(5\times 10^5\) 左右），这是完全可以接受的，因此可以贪心地将颜色划分为大小乘积比较接近的两组，折半地将两组的选法先搜出来。
假设第一组搜出来的所有选法权值扔到序列 \(a\) 中，第二组搜出来的所有选法权值扔到序列 \(b\) 中，那么现在问题就转化成了：给你两个序列 \(a\) 和 \(b\)，求 \(a_i\oplus b_j\) 的第 \(k\) 大值。
一个直接的想法是二分答案 \(mid\)，把每个 \(b_i\) 扔到 Trie 中，然后对于每个 \(a_i\) 计算有多少 \(b_j\) 满足 \(a_i\oplus b_j\ge mid\) 即可。分析下复杂度，我们令 \(T\) 表示搜一半的复杂度上界，那么时间复杂度为 \(O(T\log^2 V)\)，算下来快到 \(10^9\)，好的看来是似了。
考虑干掉二分的 \(\log\)：方法是直接让所有的 \(a_i\) 同时在 Trie 上移动。具体地，从高到低枚举答案每一位，计算每个 \(a_i\) 在当前位的相反方向上的子树内的 \(b_j\) 个数并求和，如果大于 \(k\) 说明答案这一位为 \(1\)，集体向该位相反方向移动即可，否则说明答案这一位为 \(0\)，全部向当前位的同方向移动，并将 \(k\) 减去刚刚算的个数即可。
现在的时间复杂度就是 \(O(T\log V)\) 的了，真的赢了。
标签：log,Trie,复杂度,times,问题,异或,oplus,合集 From： https://www.cnblogs.com/los114514/p/17826552.html