noip 训练 (线段树专项)

2021年11月24日 阅读数:2
这篇文章主要向大家介绍noip 训练 (线段树专项),主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

P4198 楼房重建

Description

Luogu传送门html

Solution

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

详细题解:[P4198 楼房重建 题解 - xixike]优化

P2824 [HEOI2016/TJOI2016]排序

Description

Luogu传送门spa

线段树好题。code

对于每一次操做暴力排序确定是不行的,咱们考虑用线段树优化。htm

可是普通的线段树彷佛也没法维护排序操做。观察到标签二分答案blog

emm……虽然还不知道二分答案有什么用,可是先二分了再说吧。排序

二分第 \(q\) 位的数字 \(mid\) ……而后……诶,等等。ip

排序时并不须要管数究竟是多少,只要有大小关系就足够了get

咱们把小于 \(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一下就完了……

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