P11631

· · 题解

Part 1

二分答案 x，操作可以被刻画成若干个三元组 (l,r,t)，表示将 a_{l\sim r} 全部贡献到 t 上，即要求 f(l,r,t)=\sum\limits_{l\le i\le r}a_i2^{i-t}\le x；一组 (l,r,t)_{1\sim m} 合法当且仅当：

直接 dp，需要枚举 r_i,t_i,l_i,t_{i-1}，还要进行 n 位二进制数比较、在大小为 2^nV 的解集内二分，复杂度 \mathcal{O}(n^6)。其中 t_{i-1} 的枚举可以前缀和优化掉，合法 l_i 位于一个区间内，可以二分定位然后线段树优化转移。复杂度 \mathcal{O}(n^4\log{n})。进一步的，注意到 t_i-r_i\le \log{V}，否则必有 f(l,r,t)<1 显然合法（答案显然至少为 1）。目前复杂度为 \mathcal{O}(n^3\log{n}\log{V})。

可以发现最终答案必然是某个 f(l,r,t)，如此解集大小降至 \mathcal{O}(n^3)，然后进行随机二分即可，需要解决的问题仍然是对每个 (r,t) 定位 f(l,r,t)\le f(l_M,r_M,t_M) 的 l 所在区间。复杂度降为 \mathcal{O}(n^2\log^2{n}\log{V})。

进一步的，我们优化二进制数比较复杂度。要做的是比较 f(l_1,r_1,t_1),f(l_2,r_2,t_2)，尝试求出两者 lcp，令 base 为 2 进行哈希，如此问题为求 \left\lfloor\sum\limits_{l\le i\le r}a_i2^{i-t+x}\right\rfloor，其中 i\ge t-x 的值不受下取整影响， \ge t-x-\log{V} 的贡献暴力算，l 再靠前的部分只会对哈希值产生 \le 1 的影响。形式化的描述，预处理 f_{i,j\le \log{V}}=\left\lfloor\sum\limits_{0\le k\le j}a_{i-k}2^{-k}\right\rfloor 和 g_i 为 j>\log{V} 时发生跳跃的点。可以发现：g_i 要么是 g_{i-1} 要么是 \log{V}。预处理后我们可以做到 \mathcal{O}(1) 算哈希值，复杂度降为 \mathcal{O}(n\log^3{n}\log{V})。

该做法代码写得好看一点是可以过的：https://qoj.ac/submission/2645355。

Part 2

以下部分我没有实现，属于口胡。

随 l 的减小，lcp 长度先增后减，我们求出 x=\max\limits_l\operatorname{lcp}(f(l,r,t),f(l_M,r_M,t_M))，则对于暴力 check l\in[t-x-\log{V},t-x] 的部分，l 更小的地方可以通过 g \mathcal{O}(1) 获取合法区间左端点。如何求出 x？二分 x，需 check 是否存在和 f(l_M,r_M,t_M) 往前 x 位哈希值相同的 l；将可能 ok 的 l 按 \le 和 > t-x-\log{V} 分类，前者可以通过 g \mathcal{O}(1) check，若我们做只判断前者的二分（显然也有单调性）找到一个 x'，则容易发现 x\in[x',x'+\log{V}]，且从 x'+1 开始合法的 l 区间长度就 \le \log{V}，因为 l=t-(x'+1)-\log{V} 对 x=x'+1 不合法（随 x 增加，合法 l 区间显然减小），遍历 x 再将合法 l 区间端点向中间收缩即可（check 仅需算哈希值是 \mathcal{O}(1) 的），复杂度 \mathcal{O}(n\log^2{n}(\log{n}+\log{V}))。

此时我们 dp 和二分取 mid 的部分都是 3log，以下先优化取 mid 的部分。我们希望求出 h_{r,t}=\min\limits_{f(l,r,t)\le f(l_p,r_p,t_p)}l，固定 r 时 t 增大 l 减小，对其双指针，当 t-l\le \log{V} 时我们仅需做比较一个小数点后有好几位和只有 \log{V} 位的数，预处理后容易做到 \mathcal{O}(1)，且 l 移动次数不超过 \mathcal{O}(\log{V})；否则若 t-l>\log{V} 则我们宣称：对于 t'>t，都有 h_{t',r}=1，因为次数对于固定的 l,r 随 t 增加，f(l,r,t) 变化为加上一个 <1 的数再折半，必然不大于原来的数（或者 <1）。如此对每个 r 我们仅需做一次以上求 max lcp 的二分，此处复杂度降为 \mathcal{O}(n\log{n}(\log{n}+\log{V}))。

对于 dp 部分的优化，我们倒着做，记 f_{i,j} 为 l_p=i,t_p=j 情况下 \sum t_q-l_q 最小值，每次对 j 做后缀 \min，则我们可以钦定 j=t_{p-1}+1，如此 j-i\le \log{V}。倒着扫 i，转移为：

对于固定的 j，随 i 减小 f_{i,j} 增大，故 i-1 只会转移 i 没有转移到的地方，对每个 j 维护 k 的一个指针即可。若 k+\log{V}\ge j-1，这就是单点修；否则此时变为对 i 的一个区间推平，我们宣称对每个 i 都只会做一次区间推平，这和上面关于 h_{t,r} 的原因是一致的，j 再加一就可以转移 k 就直接来到 1 了。

如此我们做到了在 \mathcal{O}(n\log{n}(\log{n}+\log{V})) 复杂度内解答该题。