2022/7/25 考试总结

时间安排

7:30~7:40

T1是做过的原题，但是记不太清楚了。

7:40~8:30

想了一会想到了T1的做法，还发现T2一直看错了题，以为是在空白部分放置矩形。

8:30~8:50

写了T3的暴力。

8:50~11:00

转化了T3之后发现可以分块，复杂是$O(n\sqrt{n}logn)$，写了一会发现可以优化到$O(\sqrt{n}+n\log n)$
但是跑的很慢。

11:00~11:30

换用了几个不同的块长，发现相对而言块长越大越快，取2000时最快。

11:30~11:50

写T2的暴力。

11:50~12:30

想了一会T2怎么做，口胡了一下可以启发式合并+凸包，但是感觉写不出来。

考后总结

T2

首先分治就没有想到，通过分治就可以把看似暴力的复杂度变得客观。
然后可以通过双指针求出对于每个点，合法的另一边的点的范围，把这些点用李超线段树/平衡树维护，同时因为有额外的限制，所以必须再套一个线段树，复杂度$O(nlo{g}^{3}n)$，不过李超线段树常数很小，所以可以通过。
另一种做法是用线段树为区间凸包，然后根据询问的斜率的单调性，均摊就可以做到$O(nlo{g}^{2}n)$。
复习了李超线段树，感觉这东西写起来非常好写，常数也小，有的时候也是不错的选择。

T3

给考场上的思路写了个题解。
[COCI2020-2021#3] Specijacija 题解
正解的话，把长链缩成一个点，然后这个新的树的点数是$O(n)$的，那么只需要知道一个点的长链编号就行了，可以从上而下使用可持久化平衡树维护，也可以从下到上使用主席树。
复杂度是$O(nlogn)$
代码也很好写，顺便复习了一下可持久化平衡树。
不过感觉平常根号的题练得比较多，使得考场上不能想出log的做法，只能根号，如果不卡常还好，如果卡常的话就很难受了。