P4198 楼房重建
Description
Solution
线段树维护斜率，pushup时记录左儿子区间最大值，把右儿子合并上去。
详细题解：[P4198 楼房重建 题解 - xixike]
P2824 [HEOI2016/TJOI2016]排序
Description
线段树好题。
对于每一次操作暴力排序肯定是不行的，我们考虑用线段树优化。
但是普通的线段树似乎也无法维护排序操作。观察到标签二分答案。
emm……虽然还不知道二分答案有什么用，但是先二分了再说吧。
二分第 (q) 位的数字 (mid) ……然后……诶，等等。
排序时并不需要管数到底是多少，只要有大小关系就足够了
我们把小于 (mid) 的数都赋为 0，大于等于 (mid) 的数都赋为 1，这样一来，对于升序操作，我们把 0 全都放到前面，1 全都放到后面，就实现了排序功能，降序排序同理。
最后我们看第 (q) 位是否为 1，并继续二分即可。
P1198 [JSOI2008]最大数
Description
Solution
这就是个线段树板子了，没什么好说的。
当然也可以用 fhq-treap 写，非常简单。
P2023 [AHOI2009] 维护序列
Description
Solution
线段树模板2……
y1s1，pushdown函数还是挺难调的，每次都得看半天。
P3224 [HNOI2012]永无乡
Description
Solution
权值线段树 + 线段树合并 (×)
(fhq-treap) + 并查集 + 启发式合并 (√)
没了……
刚开始开 (n) 棵 (fhq-treap) ，每次合并时，dfs 一遍，把较小的树合并到较大的树上。
查询的时候，查重要度排名第 (y) 小的岛的重要度是多少，然后输出该重要度的岛屿编号。
（还是非常简单的吧）
P2572 [SCOI2010]序列操作
Description
Solution
感觉是 0/1 线段树中登峰造极的题目了。
如果只维护 1 的信息，对于最多连续 1 的个数，我们发现，反转以后就无法计算了。
所以我们还要维护 0 的信息！！
于是乎……同样的代码要打两遍！
非常之毒瘤，当然写还是比较好写的，就是写完之后发现写错了的话，呵呵。
进入正题。
这道题比较难维护的就是最多连续的 1，以及区间反转操作。
连续最多的 1 其实是比较套路的，维护一个区间左边最长连续 1，以及区间右边最长连续 1，然后pushup的时候：
t[rt].maxzd = max(t[ls].maxr + t[rs].maxl, max(t[ls].maxzd, t[rs].maxzd))
就是两边的合并一下就行了。
区间反转操作：也很简单，把 0 的信息和 1 的信息全部swap一下就完了……
本人的代码目前排最优解第二，实在是卡不动了……