单侧递归线段树

· · 算法·理论

基本信息

在信息无法快速合并时，单侧递归线段树可以维护一类单点修改，区间查询问题。

如单点修改，区间询问前缀单调栈内元素个数。

需要合并左侧的信息和右侧被左侧限制的信息，通过线段树右侧向下递归的方式 O(\log n) 得到信息。

单点修改和区间查询的时间复杂度都是 O(\log^2 n)。

1

https://www.luogu.com.cn/problem/P4198

:::success[Solution] 单点修改，全局前缀单调栈元素个数，直接套模版即可。

时间复杂度 O(m\log^2 n)。 :::

2

https://www.luogu.com.cn/problem/AT_jsc2019_final_h

:::success[Solution] 维护每个位置 x 的颜色上一次出现的位置 pre_x，若第一次出现则 pre_x=0。

一个区间 [l,r] 不含有重复颜色当且仅当

\max_{i=l}^{r}pre_i<l

固定右端点 r，固定左端最小值，则合法的左端点个数为

r-\max\left(L-1,\max_{i\le r}pre_i\right)

询问 [L,R] 的答案为

\sum_{r=L}^{R}\left(r-\max\left(L-1,\max_{i\le r}pre_i\right)\right) =\dfrac{(L+R)(R-L+1)}{2}-\sum_{r=L}^{R}\max\left(L-1,\max_{i\le r}pre_i\right)

题目转换成单点修改，求区间前缀 \max 之和。

时间复杂度 O(m\log^2 n)。 :::

3

https://qoj.ac/problem/971

:::success[Solution] 离线询问，对二叉树位置进行扫描线。

对于操作 1，在 l 时刻加入 w，r+1 时刻删除 w。

注意到询问 x 时，y 产生贡献当且仅当插入 y 的时间是 [\min(x,y),\max(x,y)] 中最早的。

所以对于操作 2，答案为 a 两侧单调栈的元素下标对应原值之和。

离散化原值作为序列下标，时间作为值，维护单侧递归线段树即可。

时间复杂度 O(m\log^2 m)。 :::

4

https://qoj.ac/contest/1515/problem/8229

:::success[Solution] 离线询问，对栈位置进行扫描线。

将栈的操作序列抽象成合法括号序列，消除匹配的括号，最后一定为左侧 cr 个右括号加上右侧 cl 个左括号，本题询问元素之和 sum，所以将状态记为 (cr,cl,sum)。

可以发现 lc,rc 的合并是容易的，而 sum 的合并需要进行单侧递归。

对于操作 1，l 时刻在当前时间位置加入信息 (cr,cl,sum)=(0,x,xy)，r+1 时刻删除。

对于操作 2，l 时刻在当前时间位置加入信息 (cr,cl,sum)=(w,0,0)，r+1 时刻删除。

对于操作 3，将答案差分成前缀询问，在当前时间位置临时加入将栈内元素弹至 x 个的信息，求前缀信息即可得到答案。

时间复杂度 O(m\log^2 m)。 :::

5

https://www.luogu.com.cn/problem/CF1340F

:::success[Solution] 对任意一个区间，如果区间内部没有产生括号类型冲突，那么不断消去匹配括号后，剩余串一定形如若干未匹配右括号加上若干未匹配左括号。

我们记录哈希方便比较，并判断非法状态，所以将状态记为 (cr,hr,cl,hl,ok)。

用线段树维护信息，考虑如何合并 a,b。

若 ok_aok_b=0 或 a 右侧后和 b 左侧前 \min(cl_a,cr_b) 个不匹配，ok=0，在线段树上递归合并 hr,hl 得到目标哈希，时间复杂度 O(\log n)。

否则将多余的部分合并到新的 hr 或 hl 上，做法同上，时间复杂度 O(\log n)。

时间复杂度 O(m\log^2 n)。 :::

6

https://qoj.ac/contest/1049/problem/5098

:::success[Solution] 与 https://www.luogu.com.cn/problem/AT_jsc2019_final_h 基本相同，不过因为信息无法差分，需要再存一下合并前被限制的一侧的贡献。

时间复杂度 O(m\log^2 n)。 :::

7

https://www.luogu.com.cn/problem/P6781

:::success[Solution] 同 5，用平衡树维护区间平移即可。

时间复杂度 O(n\log n+m\log^2 n)。 :::