「Summary」2022-11-13 做题记录

哦

2022-11-13

$\mathbb{POI2011 \ PTR}$

一眼

当初其实并没有一眼秒掉，因为不会输入。
比较显然，直接在递归时决策然后合并两颗权值线段树就行了。

$\mathbb{CF \ 932F}$

同上

式子是 $dp_u = \min\{dp_v + a_u \times b_v \mid v \in \mathbb{subtree(u)} \}$ ，发现有乘积项，可以李超线段树维护，相似地，递归时合并多颗线段树即可。

$\mathbb{NOI \ 2022 \ Day1 \ T1}$

开 long long

服了，怎么这玩意这么阴，个数可以爆 int 。。。
过了才知道有个求绝对众数的方法叫做摩尔投票，但是并不影响过这道题。
有一个很好的性质，如果一个序列存在绝对众数，那么绝对众数一定是这个序列的中位数，发现可以用权值线段树很好地完成这个查询和合并，考虑怎么维护原序列，其实直接链表 $\mathcal{O(1)}$ 就能做。

$\mathbb{HEOI2016/TJOI2016 \ 排序}$

口胡快乐题

鄙人不才，线段树分裂写不对，于是就快乐地用二分加 $0/1$ 排序过了。
一个 《咦zèi！》 的思路是权值线段树的合并相当于排序，但是排序的区间的头和尾不一定是独立出来的，那么这时把他们从各自的区间分裂出来就行了。

$\mathbb{CEOI2017 \ Building \ Bridges}$

秒了秒了

一眼方程 $dp_i = sum_{i - 1} + h_i ^ 2 + (dp_j + h_j ^ 2 - 2h_jh_i - sum_j)$
直接无脑李超树上去秒掉。

$\mathbb{CodeChef \ Jump \ mission}$

这题用 cdq 会更好写吧

“ cdq 套李超树 比 树状数组套李超树 更好写。” 这是在说怪话。
方程和上一题几乎一样，注意到多了一个 $p_i \le p_j$ 的偏序性质。
那就直接在李超树外面套上树状数组就完事了，两个 $log$ 的复杂度很可以过。

$\mathbb{CodeChef \ Chef \ and \ Sets}$

相信启发式合并的复杂度！！1

启发式算法是人的算法，而我是作为一个人类在做题，所以我相信它的复杂度。
直接把小的 treap 中的元素一个一个啊塞进大的 treap 里面就行了。