线段树典题

__ryp__ · 2024-03-31 09:07:04 · 算法·理论

题意即，求整个序列中前缀最大值的数量。

考虑线段树能否维护。首先维护一个区间答案，然后考虑怎么动态维护。

线段树动态维护的方法，就是考虑左右区间的贡献，得到一个大区间的答案，然后向上递归。

那么，在这个题目里，左右区间的贡献怎么计算？

首先显然，右对左是没有贡献的。左对右的贡献，看起来很不好计算。我们来分类讨论：

左极值如果大于右极值，那么右边答案就是零
左极值如果小于右极值，这时候还不好得出结论。我们继续分讨：
左极值大于右左区间的极值，那么右左区间答案是零，我们在右右区间上递归
否则，我们考虑：既然左极值小于右左区间极值，那么右右区间受它的的影响，一定是不如受右左区间的影响的。换句话说，右右区间受不到左极值的影响。这时候，右区间的答案，就是右右区间的答案加上右左区间上递归得到的答案。

在这道题中，我们为了计算左右区间之间的贡献，需要另外做一次递归。换句话说，我们的 pushup 是 O(\log n) 的。这样，一次点修的复杂度 O(\log^2 n)。

题意为：求出最小的不能被区间 [l, r] 子集的和表示出来的数。

我们先想一下暴力怎么做。

我们维护一个 p，表示 [1, p) 的数都能表示出来。初始地，p = 1。

我们考虑怎么表示出 p。显然，能表示出 p，当且仅当存在 u \le p。如果找得到这样的 u，p\gets p + u。否则，答案就是 p。

我们考虑怎么加速。

首先更新以下策略：每次找小于等于 p 的数之和 q。如果这个和大于等于 p，由于所有的数都是小于 p 的，我们显然可以表示出 q 以内的所有数。此时 p \gets q + 1。否则,我们同样能得出答案 p。

这个过程是 O(\log V) 的，但很松。

我们再审视一下这个问题：找小于等于 p 的数之和，这就是主席树板子，在 O(\log V) 的时间可以做到。于是整体时间是很松的 O(\log^2 V)。