【题解】P5609 | 线段树 分段函数维护 人类智慧

ღꦿ࿐ · 2023-12-21 22:25:01 · 题解

对数据结构的爱，未曾衰减？

本题解参考了 Saliеri 的题解。

首先对于这类数经过操作求最终值的问题，可以比较简单地想到一个分块做法：

将序列分块，每块长度为 O(\sqrt n)，对于每一块我们需要维护某个值进去会以另外某个值出来，然后就可以在在整块上快速查询然后模拟散块，考虑这个某个值进去会以另外某个值出来的函数，令其为 f(x)，容易发现 f(x) 是一个分段函数且每段是一次函数，其段数是 O(\text{区间长度}) 的，考虑对于每个块求出这个分段函数。

维护该分段函数的分界点 k_i 进入该区间后出来且至少减去了 i 个 p 的最小值。

引理：k_i 单增且 k_i -k_{i-1}\geq p。

证明：因为 k_i 是最小的满足至少减去了 i 个 p 的值，考虑减去 i 次 p 后一定变成了 0 或负数，至少需要加上 p 才会能够继续减。

考虑增量维护 \{k_i\}，新的 k_i 发生改变仅当加上新加入的这个 a_x 后可以减去 p，即 k'_{i+1} 可以被如下更新：

需要满足能够在前面部分减去 ip 并加上 a_x 后大于等于 p，故需要满足如下条件：

且需要满足条件 p-a_x+ip < k_{i+1}，该条件意味着 能够满足在这次能被减去的数不能在之前被减去了超过 i 次，否则到该数时的值就不是 A-ip+a_x 了，可能会减去更多。

所以我们就有了个 O(n\sqrt n+m\sqrt n\log n) 的做法，但是不太能过，应该怎么继续下去找到一个 \text{polylog} 的做法？

之所以要分块是因为这个分段函数看上去很不可多元合并，只可以单元添加，如果可以多元合并就可以建出线段树，因为本题中的分段函数性质很特殊，考虑设计如下一种合并方式：

枚举在左侧和右侧的被减去的次数 kl_i,kr_j，试图判断能否在整个区间构成减去 k_{i+j} 次的情况，记录左侧的和为 S，则有如下更新：

类似上面，若满足条件 kr_j - s + ip < kl_{i+1} 才可以去更新，即在左侧被减去了 i 次，否则会减去 i+1 次或更多。

对于满足条件的 i,j 有如下更新：

直接枚举 i,j 并进行合并的复杂度是平方的，我们继续挖掘性质。

令 V(i,j)=\max(kl_i,kr_j-s+ip)。

定理：对于一个固定的 i+j，被 i 最小的 i+j 更新到是最优的。

证明：试比较 V(i,j),V(i+1,j-1)，因为有 kr_j - s + ip < kl_{i+1}，所以一定有 \max(kl_i,kr_j-s+ip) < \max(kl_{i+1},kr_{j-1 }-s+ip)。

所以我们只需要对每个 i + j 求出最小的 i 可以去更新它，又因为可以更新的条件是 kr_j - s < kl_{i+1} - ip，随着 i 增大而越来越松，所以用双指针枚举最大的 j 即可。

于是我们求出了所有线段上的分段函数的形态，查询时直接在线段树上依次对 O(\log n) 个分段函数进行二分，时间复杂度 O(n\log n + m \log^2 n)。