2023.8
1. Good Subsegments
这个已经是典中典题了。
首先考虑一个段合法等价于 \(mx - mn = r-l\)，也就是 \(mx-mn-r+l = 0\)，而且注意到 \(mx-mn-r+l\ge 0\)，所以如果我们全局询问的话，那就是扫描线维护，然后维护一下全局的最小值以及最小值个数就行了。
然后区间的子区间计数就考虑套维护历史信息的 trick，也就是我们还是维护扫描线的过程。操作是区间加。
然后询问的东西实质上有点牛魔的：相当于给出一个区间 \([l,r]\)，首先要求这些位置的历史最小值的 \(\min\)，设为 \(x\)，还要求出每个位置历史值 \(=x\) 的次数和。
这个东西手搓了一下竟然自己手搓出来了：考虑对每个位置维护一个三元组 \((min,cnt,sum)\)，表示该位置的历史最小值，以及历史最小值个数，还有当前的值，那么原序列上的加法（对应这个三元组的乘法）是容易的：\(+a\) 等价于乘上 \((a,1,a)\)；但是我们用线段树的话，首先就需要定义加法，然后还需要满足分配律。
加法的话比较牛魔，先不考虑分配律，那就是 \(\min\) 是两个人的 \(\min\) 取最小值；然后 \(cnt\) 跟着算，然后 \(\sum\) 也得取 \(\min\)。但是发现他好像不满足分配律：两个一样的三元组，合并起来的话以后都是要当两份算的，但是没有体现出来。所以还要记录一下有多少个位置他的 \(sum = \min sum\)，这个四元组的加法乘法满足分配律，然后就可以 seg 打 lazy 维护了。
时间复杂度 \(O(n\log n)\)。
记录
2. Ping-Pong
我咋感觉这个非常难啊？？
题目的约束告诉我们如果 \(A\) 严格包含 \(B\) 则 \(B\) 能到达 \(A\)；如果相交不包含则可以互相到达。
如果只有第二类关系，则维护可达性是非常容易的，可以用 dsu 维护，在线段树上加速：注意到区间单调增的限制，所以加入 \((l,r)\) 的时候一定没有区间包含他；我们只用算多少区间覆盖了 \((l-1,l+1)\) 和 \((r-1,r+1)\) 这两条线段（二者选其一，且一个线段最多也只满足其一）就好了，然后就可以用 seg 辅助维护。
第一类关系就很复杂感觉，但有这样一个性质：若 \(A\) 严格包含 \(B\)（实际上本题没有相等的区间），则 \(A\) 所在的连通块一定包含 \(B\) 所在的连通块。
根据这个性质我们只会在开始的时候走最多一次第一类单向边，他也等价于 check 终点的所在连通块区间是否包含起点所在的连通块区间（注意这里非严格）。
但是这个非常坑啊，注意到 observation 的表述是包含，而非严格包含；虽然给出的区间没有相等的，但是可能两个不同的连通块，他们代表的区间范围是完全相等的。
可以发现这种情况下 \(A\) 不能到 \(B\) 当且仅当 \(A\) 本身构成一个连通块，且其等于 \(B\)，判掉就好了。
记录