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}$ 合法当且仅当：

• $l_i=r_{i-1}+1,l_1=1,r_m=n$。

• $l_i\le r_i\le t_i$，$t_{i-1}\le t_i$。

• $\sum t_i-l_i\le k$。

直接 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$ 的后缀 $\min$。

• 枚举 $k=l_{p-1}

对于固定的 $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}))$ 复杂度内解答该题。