单侧递归线段树

· · 算法·理论

UOJ515 前进四

维护长为 n 的序列 a_i,支持 q 次操作:

  • 给定 i,x,令 a_i \gets x。
  • 给定 x,求 [x,n] 中严格后缀 \min 的数目。

:::::warning[注意]{open} 下面讲的做法无法通过,只是从这个题引出单侧递归的思想。 :::::

:::::success[题解]

使用单侧递归线段树的技巧,可以 O(q \log^2 n) 地在线解决这个问题。

我们在线段树节点 [l,r] 上,维护该区间的最小值 \text{mn} 和仅考虑 [l,r] 内后缀 \min 的数目 \text{cnt},尝试构造可合并信息。

合并区间 [l,m] 和 (m,r] 时,容易发现 (m,r] 的答案 \text{cnt} 不会变化。已知右区间最小值为 v,考虑对 [l,m] 递归查询正确的 \text{cnt}。

这样,我们在查询时始终保持单侧递归,单次 pushup 的复杂度为 O(\log n),整个问题的复杂度为 O(q \log^2 n),2log 难以通过。

:::::

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[题解]

套路地令 p_i 为 j<i \land a_i=a_j 的最大的 j。则好区间被刻画为 \forall i \in [l,r], p_i <l,即 \max \limits_ {i \in [l,r]} p_i<l。

枚举 r,则合法的 l 满足 l \in [x,r] 且 l> \max\limits_{i=l}^r p_i。注意到 \forall i < l, p_i < l-1,将条件放缩为 l> \max\limits_{i=1}^r p_i。记 q_r=\max\limits_{i=1}^r p_i,则 l \in [x,r] \cup (q_r,+\infty),从而答案为

\sum \limits_{r=x}^y (r-\max(x-1,q_r)) = \dfrac{(x+y)(y-x+1)}{2}-\sum \limits_{r=x}^y \max(x-1,q_r)

使用 std::set 维护每种数的出现位置,容易将对 a 的单点修改转化为对 p 的 O(1) 次单点修改。

我们用线段树维护 p 数组,询问对 [x,y] 求前缀 \max 之和。使用单侧递归线段树解决,将 x-1 作为递归查询的初始限制即可,单侧递归的逻辑类似。

复杂度 O(q \log^2 n)。代码。

:::::

CF1340F Nastya and CBS

维护长为 n 的括号串 S,共有 k 种括号。支持 q 次操作:

  • 给定 i,c,令 S[i] \gets c。
  • 给定 l,r,查询 S[l:r] 是否为合法括号串。

:::::success[题解]

单侧递归线段树维护区间不匹配括号信息。

考虑用线段树维护 S,节点上维护失配括号信息。若某段区间出现了形如 \tt{(]} 的子串,则区间必然不合法,直接标记为失败。

根据观察,失配的括号必然形如 \tt{))\cdots)} \tt{((\cdots (},这里括号只表示方向而不表示种类。

用多项式哈希分别维护左右两部分,合并信息时需要抵消靠近中线的括号对。那么合并时必然消掉左子树的后缀,或者右子树的前缀,否则标记为失败。

为处理括号种类的限制,我们需要查询前 x 个失配括号的哈希值,以判定是否可以抵消,在对应子树中做线段树二分即可。查询过程是单侧递归,需要一些讨论。

对于询问,我们拉出线段树上的 O(\log n) 个节点,新建若干虚点并复用 pushup 过程即可。

复杂度 O(q \log n)。代码。

:::::