单侧递归线段树
stripe_python · · 算法·理论
UOJ515 前进四
维护长为
n 的序列a_i ,支持q 次操作:
- 给定
i,x ,令a_i \gets x 。- 给定
x ,求[x,n] 中严格后缀\min 的数目。
:::::warning[注意]{open} 下面讲的做法无法通过,只是从这个题引出单侧递归的思想。 :::::
:::::success[题解]
使用单侧递归线段树的技巧,可以
我们在线段树节点
合并区间
-
我们先判掉下图所示的情形,区间最小值
\ge v 时不会产生新的后缀\min : -
叶子节点终止递归,否则考虑当前节点的两个儿子。
-
若右儿子的
\text{mn} \ge v ,则右儿子不产生新的后缀\min ,对左儿子复用v 的限制进行递归即可。 -
若右儿子的
\text{mn} < v ,则对右儿子递归。此时左儿子的限制是右儿子的\text{mn} ,而这个值已经在pushup时正确计算,直接复用即可。
-
这样,我们在查询时始终保持单侧递归,单次 pushup 的复杂度为
:::::
AT_jsc2019_final_h Distinct Integers
维护长为
n 的序列a_i ,支持q 次操作:
- 给定
i,x ,令a_i \gets x 。- 给定
x,y 。定义区间[l,r] 是好的,当且仅当a_l \sim a_r 互不相同。求[l,r] \subseteq [x,y) 且[l,r] 是好区间的[l,r] 数目。
:::::success[题解]
套路地令
枚举
使用 std::set 维护每种数的出现位置,容易将对
我们用线段树维护
复杂度
:::::
CF1340F Nastya and CBS
维护长为
n 的括号串S ,共有k 种括号。支持q 次操作:
- 给定
i,c ,令S[i] \gets c 。- 给定
l,r ,查询S[l:r] 是否为合法括号串。
:::::success[题解]
单侧递归线段树维护区间不匹配括号信息。
考虑用线段树维护
根据观察,失配的括号必然形如
用多项式哈希分别维护左右两部分,合并信息时需要抵消靠近中线的括号对。那么合并时必然消掉左子树的后缀,或者右子树的前缀,否则标记为失败。
为处理括号种类的限制,我们需要查询前
对于询问,我们拉出线段树上的
复杂度
:::::