T1

更新的本质是把当前点向后的所有的值域上的数构成的逆序对清空

那么影响应该是后面所有的清空，前面比这个点大的减掉这个点的答案

考虑每次更新之后矩形框的答案

更新之后矩形框就空了，所以答案就没有了

存在答案的点的减少的总量是 (O(n)) 的

考虑如何维护这个值

用 (vector) 存下来所有的位置，每个点带着一个答案

考虑更新的时候遍历所有比这个点小的 (vector)

在每个点里面二分得到 (sum)，并且删掉所有的对应位置

以上是考试的时候的思路，因为数据是随机的，所以过掉了

然而两个序列都上升直接卡飞

正解其实类似，考虑用线段树来维护区间的最小值之后推平就行了

因为每个点只会被删掉一次，所以就是 (Theta (nlog n))

考场上有个变量没清空，所以少了 (40)

T2

这题目更坑，直接 (40 o 0)

具体原因很可笑，我读入的时候根本没有读进来 (b) 数组

没看清输入格式直接乱打一通

以下正解，会了多少就写了多少

首先这种随机的树有一下性质：

(1.) 深度是 (log n) 的

(2.) 子树大小 (siz_ile frac{n} u)

(3.) 树上每个点的度数是 (log n) 级别的

这里的状态定义是利用了深度很小来做的：

(f_{x,st}) 表示从 (x) 到根的状态为 (st) 的时候 (x) 可以贡献的美丽度

（其实挺懵的，并不懂题目里的限制用这个状态怎么处理的，不过是符合那个啥小压啥的原则……）

然后设 (g_{x,st,i}) 表示 (x) 的子树里面有 (i) 个点被点亮同时 (x o rt) 的状态是 (st) 的方案数

这个转移考虑树形 (dp) 做背包即可

这题目转化真狠，理解起来十分费劲