线段树典题

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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)$。

ryp 的博客