日记

不考试 day。

本来想写可持久化学习笔记的，但是想了想，不想画可持久化线段树的图，于是放弃了。

[NOI2018] 归程# Link to

前天的可持久化并查集双 $\log$ 的做法爆炸了，于是只能去写单 $\log$ 的 Kruskal 重构树。

我们按照海拔建一个小根的重构树。那么倍增调到 $u$ 的最上面的祖先 $v$，满足它的点权大于查询的海拔。那么 $v$ 的子树内肯定都是 $u$ 开车能到达的。于是我们就能做了。

[TJOI2018] 异或# Link to

先剖了再说。

我们把树剖成链了，那么链上的区间异或不就好做了吗？直接可持久化 Trie。

[POI 2014] KUR-Couriers# Link to

自己找了一道主席树的题来做。

我们看到“出现次数严格大于区间长度的一半”，如果对于整个的 $[1,n]$ 的区间，那么权值线段树肯定很好做，那么可持久化一下就可以做区间的了。

[FJOI2016] 神秘数# Link to

我们考虑对于一个区间来说怎么做：先从小到大排序，如果当前能表示出来的数集为 $[1,x]$，如果有 $a_i \le x$，那么区间变成 $[1,x + a_i]$，反之就表示不出来 $x + 1$。于是我们可以用主席树维护一段区间内小于 $x$ 的数的和。如果没有了，那么就是答案了。