desive 题解

Tony2 · 2024-11-17 14:56:26 · 题解

以下做法感觉和官方题解意思差不多。

记 ans_{l,r} 表示 [l,r] 的 xormex，通过打表先猜测有用的区间数量是 2^n \times n 的量级的。一个有用的区间指的是所有自己区间的答案比所有自己包含的区间的答案要大的区间。

这样最后需要得到的信息就是一堆三元组 (l,r,k) 表示区间和对应答案。题目问的东西不过是矩形加矩形求和。

把所有输入的数按照二进制建立 01trie，这个信息可以在 trie 上的每个节点计算。具体的，一个节点代表了一个值域区间 [lv,rv)，只要算出保留所有 a[i]\in[lv,rv) 的 i 后的三元组信息即可。

假设对于一个 01trie 节点已经算好了子树的答案，如何计算当前节点的答案？

因为真正保留所有有用的区间没法做到最终 2^n \times n^2 的复杂度，所以可以在区间数量上限依然是 2^n \times n 的前提下留一些没用的区间。

设 len=rv-lv，v[k] 表示固定了 k 后所有答案 \ge k 的区间的集合（即有用区间及包含他们的区间），同样表示 vl 和 vr 表示左右子树。

对于 k\in[1,len/2]，有 v[k]=vl[k]\cup vr[k]。对于 k\in[len/2+1,len]，有 v[k]=(vl[k-len/2]\cap vr[len/2])\cup(vr[k-len/2]\cap vl[len/2])。

并的部分直接把有用区间加起来即可。但是交的部分需要仔细考虑：

例如考虑 vl[k-len/2]\cap vr[len/2]。vr[len/2] 是一个轮廓线，对于 k-len/2 的所有有用区间集合 S，最后可以看作求 \cup_{\forall seg \in S} seg\cap vr[len/2]。

观察区间（左上矩形）交轮廓线后的结构，若区间在轮廓线内，则直接添加自己；若区间不在轮廓线内，轮廓线的右下突起角（即新的有用区间）由左下、右上两个新的有用区间和中间轮廓线上的有用区间构成。

假设添加这些所有区间，区间数量肯定是不行的；但是分别考虑这两种区间，假设两个 k 同时出现了相同的区间，那么显然应该保留大的 k 的区间。对于新的有用区间，其实在 vl[1]\cap vr[len/2] 中会全部出现，这意味着总共新的不同的有用区间个数只有子树大小（指在原序列上的个数）的两倍（一左一右），每个新区间最后保留一个；对于轮廓线上的有用区间，同样每个有用区间只会保留一个（最终都会出现在 vl[len/2]\cup vr[len/2] 中）。对于上面区间在轮廓线内的情况，同样最终也只保留一个。

这里应该有一张图片：

其中蓝色代表新加的有用区间，绿色代表轮廓线的有用区间。

也就是说上述区间总数就是两个儿子的区间总数加自己新添加的区间数量，即加上了两倍子树大小（原序列在值域区间上的元素个数）。这样每个节点的有用区间个数上限就是 2size\times de 个。

至此我们从做法上构造性证明了原本关于有用区间个数的结论，以下给出具体的算法。

关键在于如何求交。对于新添加区间，找到投射在轮廓线上的新区间并不难，因为最后新的有用区间只有线性个，所以可以预处理好，简单查对应的 k 即可。对于轮廓线上的区间，从大到小枚举 k 相当于在不停的删轮廓线上的有用区间，删的是一个区间的，这个问题可以用经典的线性序列并查集解决。最终算法的复杂度是关于所有节点有用区间总数 2^n\times n^2 的线性，即复杂度依然为 O(2^n\times n^2)。