出题: Chielo, 验题: skywalkert。
简明题解：DFS + 维护后缀AND和区间 + 寻找后缀最小值的变化点。
题解#
直接在有向树上进行 DFS，将走过的边权视为序列 \(a_1, \cdots, a_n\)，题面所需的就是后缀AND和与后缀最小值相等的情况有多少种。
算法需要保证在维护所需信息的同时，可以支持在该序列末尾加入一个元素、回退加入元素，这两种操作。
考虑两个相邻的后缀AND和 \(A_i = \mathrm{AND}(a_i, \cdots, a_n)\), \(A_{i-1} = \mathrm{AND}(a_{i-1}, \cdots, a_n)\)，有 \(A_{i-1} = \mathrm{AND}(a_{i-1}, A_i)\)，显然，\(A_i\) 随 \(i\) 的减小而不严格递减。并且，若 \(A_{i-1} \ne A_i\) 的话，则说明\(A_i\) 的二进制中至少一个 \(1\) 变为了 \(0\)，所以 \(A_i\) 的取值只有 \(\mathcal{O}(\log{a_i})\) 种，并且连续的若干 \(A_i\) 会取到相同的值。
后缀最小值 \(M_i\) 的分析也同理，随 \(i\) 的减小而不严格递减，但取值是有 \(\mathcal{O}(n)\) 种。若 \(M_{i-1}=\min(a_{i-i}, M_i) \ne M_i\)，则 \(M_{i-1} = a_{i-i}\)。
因此，最方便的做法是 DFS 过程中，用数组或者链表维护后缀AND和区间，即 \(i\) 处于某区间 \([l, r]\) 时，后缀AND和等于定值 \(A\)（DFS后继的话用祖先的区间链表更新一下就行）。然后寻找后缀最小值 \(M_j\) 何时恰好等于 \(A\)，即令 \(j\) 最大。再想，后缀最小值 \(M_j\) 能恰好减小到 \(A\)？应当是满足 \(a_j=A\) 且 \(j\) 最大的那个元素 \(a_j\)。这个东西用哈希表维护一下每个元素值最大的下标就好。
（不理解可以画后缀最小值与后缀AND和的图像，找找什么时候函数值相同。）
回退的话，我们维护的区间存起来就行，空间存得下；哈希表因为每次只会改一个映射，递归完恢复一下就可以。不用哈希表也可以，因为映射的值就那 \(\mathcal{O}(n)\) 个，可以离散化，用数组存，复杂度虽然劣一些，但是常数较优，跑的反而快很多。
比赛结果分析#
这一道题，确实是乱搞题。
但是因为比赛时的数据边权几乎是随机的（忘记处理了），比赛的最后时刻，一名校内的大一选手大胆猜测，写了个 \(\mathcal{O}(n^2)\) 暴力+剪枝，拿了现场赛唯一的 Accepted（现在 OJ 上另外加了数据增强的题目了，但是数据范围没变）。
网络赛中，唯一的 Accepted 提交来自栗子老师，（似乎是）用的二分+ST找最小值的位置；怎么维护的AND和区间没看懂，空间复杂度是 \(\mathcal{O}(\log{a_i})\) 的（似乎是找每一位在哪一深度被置为 \(0\)）；如果不用二分+ST应该是最优的做法吧；在DFS过程中更新ST，这一点值得学一下。
标程#
使用 unordered_map，时间复杂度 \(\mathcal{O}(n\log{a})\)，空间复杂度 \(\mathcal{O}(n\log{a})\)。
离散化，时间复杂度 \(\mathcal{O}(n\log{n}\log{a})\)，空间复杂度 \(\mathcal{O}(n\log{a})\)。
评论