- 感觉这一部分理解地比较困难，比较久，莫非是文化学太久脑子生锈了。。。
- 引入了一个名叫势能的概念，我理解的主要思想是说把一个势能为0的线段树节点 \([L,R]\) 打上标记，这样以后就可以对它进行整体处理，再计算原本有的势能以及会增加的势能得出一个复杂度合法的方案
- 把势能按照重力势能去看待则它<=初始势能+均摊势能的和 区间极差
- C - 基础数据结构练习题
- JLY大神通过极差来去弄它们之间的关系，并发现若对于最大值为 \(y\) 最小值为 \(x\) 的区间开根，开完后的 \(y_1-x_1 <= \sqrt{y-x} + 1\)
- 故我们能得到总势能 \(\sum_{[L,R]} log log (y-x)\)
- 我们再特殊讨论一下极差为1的情况，发现如15，16它们会变成3，4这时候极差没有改变，故我们可以 通过极差是否改变来选择是否打标记，像这种极差没有改变的直接打减法标记，其他的暴力开方
- 故我们考虑如何看待区间加操作，首先显而易见的如果一个区间是完全相同的话那么可以直接打标记，反之则极差最多增加\(v\) 故一个区间在线段树上由 \(log_{n}\) 个节点组成，故我们可以得到它所增加的势能为 \(q \cdot log_{n} \cdot \log \log_{v}\)
- 故我们总的时间复杂度就是 \(O (N \log \log v + q \cdot \log_{N} \cdot \log \log_{v})\)
- 代码一开始写的比较复杂，写到一半进行了调整。
- B - 市场
- 还是看差值，初始的势能是 \(N \log_{N}\) 会增加的势能是 \(N \log_{N} \log_{N}\) 然后同理做即可。(8,7像上述的方案一样处理)
- D
- 三个操作
- 区间赋值
- 设 \([L,R]\) 的 \(mex\) 为 \(w\) 则将 \([L,R]\) 中的所有数加上 \(w\)
- 区间求和
- 对于一个修改区间，我们依次找到该区间的最小值，并把线段树区间内等于最小值的叶节点的所有数加上INF。重复以上过程，直到找到mex，再还原叶节点并打上加法tag。（注：还原的时候只要这个区间内的所有数都大于INF就让这个区间整体减去一个INF即可还原）
- 对于区间加上 mex 的操作我们能发现对于小于 \(mex\) 的数进行这个操作的时候至少会翻倍！故我们能发现一个数最多进行 \(log_{N}\) 次翻倍，一次翻倍的代价是找出那个叶子节点进行翻倍 O(\log_{N})
- 复杂度为 \(O(N \log_{N} ^ 2)\)
- 对于区间赋值操作我们可以打一个区间赋值tag，在整个区间已被推平时不继续遍历即可。是 \(O(N \log_{N}^3)\) 的，JLY大神说可能需要仔细分析，但是我不会分析我也没找到分析这个的题解，加上这个复杂度本身就是跑不满的，主要还是学习均摊的这种思想，所以就这样吧。
- E
- 势能是 \(\sum_{[L,R]}\) 的不同数的个数
