noip 训练 （线段树专项）

P4198 楼房重建

Description

Luogu传送门

Solution

线段树维护斜率，pushup时记录左儿子区间最大值，把右儿子合并上去。

详细题解：[]

P2824 [HEOI2016/TJOI2016]排序

Description

Luogu传送门

线段树好题。

对于每一次操作暴力排序肯定是不行的，我们考虑用线段树优化。

但是普通的线段树似乎也无法维护排序操作。观察到标签二分答案。

emm……虽然还不知道二分答案有什么用，但是先二分了再说吧。

二分第 \(q\) 位的数字 \(mid\) ……然后……诶，等等。

排序时并不需要管数到底是多少，只要有大小关系就足够了

我们把小于 \(mid\) 的数都赋为 0，大于等于 \(mid\) 的数都赋为 1，这样一来，对于升序操作，我们把 0 全都放到前面，1 全都放到后面，就实现了排序功能，降序排序同理。

最后我们看第 \(q\) 位是否为 1，并继续二分即可。

P1198 [JSOI2008]最大数

Description

Luogu传送门

Solution

这就是个线段树板子了，没什么好说的。

当然也可以用 fhq-treap 写，非常简单。

P2023 [AHOI2009] 维护序列

Description

Luogu传送门

Solution

线段树模板2……

y1s1，pushdown函数还是挺难调的，每次都得看半天。

P3224 [HNOI2012]永无乡

Description

Luogu传送门

Solution

权值线段树 + 线段树合并 (×)

\(fhq-treap\) + 并查集 + 启发式合并 (√)

没了……

刚开始开 \(n\) 棵 \(fhq-treap\) ，每次合并时，dfs 一遍，把较小的树合并到较大的树上。

查询的时候，查重要度排名第 \(y\) 小的岛的重要度是多少，然后输出该重要度的岛屿编号。

（还是非常简单的吧）

P2572 [SCOI2010]序列操作

Description

Luogu传送门

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一下就完了……

本人的代码目前排最优解第二，实在是卡不动了……