楼房重建
转化为单点修改，求前缀最大值的数量。
分块可以做到 $O(n\sqrt{n\log n})$。
建线段树，对于每个节点维护区间前缀最大值的数量 $len$ 和区间最大值 $mx$。考虑节点的合并，只要能快速求出 $calc(id,v)$ 表示在节点 $id$ 中，以 $v$ 开始的前缀最大值的数量即可。
- 若 $id$ 为叶子节点，判断 $mx$ 与 $v$ 的大小即可。
- 若 $id$ 不为叶子节点
- 若 $v>=mx(id)$ 那么答案为 $0$。
- 若 $v>=mx(lc)$ 那么答案为 $calc(rc,v)$。
- 否则答案为 $calc(lc,v)+len(id)-len(lc)$。
每次只会往单侧递归，所以时间复杂度 $O(\log n)$。
总时间复杂度 $O(n\log^2n)$。
离线技巧
1.【UR #19】前进四
用上述算法可以做到 $O(n\log^2n)$，过不去。
求解的区间是一段后缀，较为特殊。
考虑对序列倒着扫描线，用数据结构维护时间。
对当前位置的每个赋值都可以找到一段有效时间区间。
区间取 $\min$，答案即为某个点被成功取 $\min$ 的次数。
用 segment tree beats 维护，时间复杂度 $O(n\log n)$。
2.TEST_155 pmphms
维护两个初值为 $0$ 的序列 $a,b$，每次对 $a$ 单点修改，$b_i$ 加上 $\max_{j=1}^{i} a_j$，查询 $\sum_{i=1}^{x} b_i$。
没看明白。。。
转化问题
1.无题
维护一个序列，支持单点修改，查询一段区间中有多少个不含重复元素的子区间。
强制在线，$1 \le n,m \le 3 \times 10^5$。
记 $lst_{i}$ 为 $i$ 前面第一个与 $a_i$ 相同的数的位置。
对于固定的右端点 $x$，合法的左端点具有单调性，其范围是 $[\max_{i=1}^{x}+1,x]$。
线段树二分，求前缀最大值之和即可。
2.无题
定义一段区间是好的，当且仅当区间内部第 $i$ 个数 $\ge i$。
维护一个序列，支持单点修改，查询一段区间有多少个子区间是好的。
$1 \le n,m \le 10^6$
只会双 $\log$。
维护未匹配括号序列
1.Nastya and CBS
建线段树，每个节点维护本区间匹配后的括号序列，它一定类似 ‘]))[(‘ 不然不合法。
考虑如何合并，发现每次左右儿子中间的括号会有一个被删完。
维护左右括号的数量和哈希值，通过个数可以判断哪个儿子的括号被删完，个数也是好维护的。
只需要快速求出某个节点前 $k$ 个右括号（和后 $k$ 个左括号） hash 值即可。
以前 $k$ 个右括号为例
若 $lc$ 右括号的数量 $\ge k$，递归进 $lc$。
否则为 $lc$ 的右括号和 $rc$ 的某段右括号拼接，递归进 $rc$，再减去前面一段即可。
单侧递归，总时间复杂度 $O(n\log^2n)$。
2.[Ynoi2008] rupq
由于要支持区间 swap，用 FHQ-Treap 维护。
需要查询某个节点前 $k$ 个左括号（和后 $k$ 个右括号）的信息。
这个单侧递归可以做到 $O(\log n)$。
对于 $\texttt{NAND}$ 的信息合并，维护全 $0$ 和全 $1$ 经过操作后得到的结果，$O(1)$ 合并
1 | ans_0 = (~l_0 & r_0) | (l_0 & r_1) |
特殊之处在于每个节点需要维护两个儿子合并后中间剩下那段的信息。
杂题
1.[PKUSC2021 D1T2] 逛街
考虑用平衡树维护连续段段，开始每个数为一个连续段（值相同的排在后面的小）。
每次操作，连续段的长度可能 $+1/-1/不变$。需要快速找到原序列对应的位置和要删除哪些点。
对于前者，维护连续段的总长即可。
对于后者，要删除的连续段肯定是每次操作 $-1$ 的，对这些段单独维护长度的最小值，每次暴力找出长度 $=0$ 的删除即可，这样均摊是对的。
对于查询，用单侧递归线段树维护。
2.[PKUWC2024 D2T3] 栈
对编号扫描线，用数据结构维护时间。
将压入看作左括号，弹出看作右括号，维护匹配后的括号序列和权值和。
每次要支持加入一些左/右括号，对于删除特定的左括号。
每个时间只会有一次操作，不知道我在想什么。
3.「LibreOJ NOI Round #2」小球进洞
4.完全动态凸包
平衡树套可持久化平衡树。
参考
lxl 的 ppt。