数据随机下区间点对最优化的乱搞

· · 算法·理论

针对数据随机下全局点对最优化容易实现而区间点对最优化难以实现的乱搞。

本乱搞基于数据随机且可以离线。

本乱搞有一定的应对非随机数据的能力，不依赖于询问随机，只依赖于权值随机。

乱搞思想核心基于区间内随机选两个点期望在两个三等分点附近，以及对分治总长度和块长进行平衡。

给出一个 题目应用。

这道题是求区间最接近且不相等的两数之差的绝对值。

设 n 与 q 同阶。

首先需要一个求全局点对最优化的做法，时间复杂度为 O(nK)，K 为时间复杂度除 n 以外的部分。以上述问题为例，K=\log n，做法为先排序后直接计算。

做法为对询问离线然后进行分治。

设一个区间 [l,r] 的区间最优化点对位置分别为 p,q，最优化答案为 s。

因为数据纯随机，可以认为 p,q 在 [l,r] 之间随机分布，即 p,q 大概在 [l,r] 的两个三等分点上。

考虑分治，对于一个区间 [l,r]，设阈值 T，如果长度不大于 T 暴力即可。

在当前区间 [l,r]，找出对应的 p,q，包含于此区间的所有询问区间可以划分成三部分：

第一部分的答案都等于 s，不需要继续分治。

然后对区间 [l,q) 和 (p,r] 分治。

按照随机进行分析，即每次的 p,q 都在 [l,r] 的三等分点上。

如果每次分治三个部分都存在询问区间，每次总长度会乘 \frac{2}{3}+\frac{2}{3}=\frac{4}{3}，每段长度会乘 \frac{2}{3}。

设分治某一层的总长度为 m，那么处理这一层的时间复杂度为 O(mK)，这个 m 每层都会乘 \frac{4}{3}。

比 1 多出来的 \frac{1}{3} 是第二三部分重叠部分。

观察 \frac{2}{3} 和 \frac{4}{3}，考虑把两个数进行均摊。当 n=100000 时，进行 15 层分治区间长度即可达到 228，而对首项为 1，公比为 \frac{4}{3} 的等比数列的前 15 项求和，结果为 221。这个 221 表示前 15 层所有段的总和有有 221n，也就是 2\times 10^7。然后每次排序乘上一个 \log n，运算量上界为 2\times 10^8。

再进行平衡分析。设 A=3\times \left( \frac{4}{3}\right)^x，B=n\times \left( \frac{2}{3}\right)^x，其中块长 T=B。分治复杂度为 O(nAK)，小块暴力复杂度为 O(nBK)，也就是说对 A 和 B 进行平衡。

经过推导 T=\frac{n^2}{3\times \left( \frac{n}{3}\right)^{\log_2{3}}}，是 n^{0.415} 的量级，大概是 2n^{0.4}。总时间复杂度为 n^{1.415}K。

因为有大量属于第一部分的答案，还有不少第二三部分的为空，实际上达不到上限。

最后再说一个优化，每次 l 和 r 可以分别取询问集合 Q 中左端点的最小值和右端点的最大值。

从表现来看，常数极小，跑的比一些其他的乱搞和两只 \log 的做法快几倍。

以上复杂度分析仅供参考，好像时间复杂度是不能直接按照期望分析，如果有错误请大佬指出。

来说一下应用。

区间两个数的异或最大值，这个如果用正常做法来做非常困难，但如果用上述方法可以直接套一个 Trie 树，在出题人不卡的情况下很有可能把 std 按在地上打。

把“点对最优化”的点对看成区间左端点和右端点，即可拓展到“区间内区间最优化”。

例如查询给定 [l,r] 内的一个区间使得找到的区间最大值乘最小值最大，多次给出 [l,r]。

update on 2024.7.28

暂未找到其他应用题目，如果有请联系作者。

update on 2024.11.17

应用题目：https://qoj.ac/contest/1835/problem/9613