STO lxl orz
CodeForces-526F Pudding Monsters *3000
等价于给一个排列，问有多少区间 \([l,r]\) 排序后是连续的，这个区间覆盖问题是经典套路，等价于 \(\max-\min=r-l\)，也就是 \(\max-\min-r+l=0\)。
使用线段树+单调栈，枚举右端点，对单调栈每个元素维护其作为最值且右端点是 \(r\) 的左端点范围，弹栈时撤去贡献，批量处理在线段树上进行。
由于原数组是排列，所以 \(\max-\min\ge r-l\)，维护最小值和最小值个数就可以。
单调栈均摊，复杂度 \(O(n\log n)\)。
大致可以撤销的 \(\max\) 与 \(\min\) 统计问题都可以这么做，不可撤销的例如没有逆元的乘积需要另一个做法——分治。
对区间 \([l,r]\) 分治中心 \(mid\) 处统计跨过 \(mid\) 的区间的答案，有四种情况，分别对应最大值与最小值出现在左区间还是右区间，设 \(mx_i\) 表示 \(i\) 到分治中心的区间内最大值，具体要看 \(i\) 在左右哪个区间，\(mn_i\) 同理。
如果两个最值都出现在左区间，那么可以确定 \(j=i+mx_i-mn_i\)，判断是否合法即可，都出现在右区间同理。
如果出现在不同的区间，假设最大值出现在左区间，从右到左枚举区间左端点 \(i\) 这样对应右端点 \(j\) 应当满足 \(mn_j<mn_i,mx_j<mx_i\)，前一个条件对应一个后缀且不断缩小，后一个前缀对应一个前缀且不断扩大，所以二者的交应当是不断右移的，可以双指针维护一个合法的区间，判断 \(j-i=mx_i-mn_j\) 就改成 \(i+mx_i=j+mn_j\)，开桶处理，另一种情况同理。
CodeForces-464E The Classic Problem *3000
高精度二进制最短路，也就是需要支持比较大小和加法两个操作。
先考虑用怎样的数据结构去存储，这里 01-Trie 肯定是不行的，最劣会到 \(O(n^2)\)，而每次修改要么是在 \(0\) 上加 \(1\) 要么是给一个 \(1\) 连续段全部赋值成 \(0\) 再给更高一位加 \(1\)，也就是进位操作，发现其实是在转移节点的最短路基础上修改，所以可持久化线段树比较合适。
比较操作一定是在线段树上一起走，类似找 \(\mathrm{LCP}\)，找到最高的不一样的一位即可，那么就需要快速比较右子树是否相等，哈希就行，在此基础上，求 \(1\) 连续段也就自然二分处理了。
那么线段树就要维护子树哈希值和一个区间修改标记，可持久化所以要标记永久化。
一个特殊之处是如果当前区间打了一个标记，但修改时又在区间某个位置加 \(1\)，这个标记要撤去，但是不能下传，所以其中一棵子树（单点修改不经过的一棵）是要新建一个节点打上标记的。
这样堆内部排序以及二分都是两个 \(\log\)，空间上每次更新最短路就会新增一个版本，于是时间复杂度 \(O(m\log n\log x+m\log^2 x)\)，空间复杂度 \(O(m\log x)\)，由于是区间修改，空间尽量开大。