2022/7/26 考试总结

时间安排

眼镜坏了，发挥不好。

7:30~8:20

看出T1的$n\sqrt{n}$ 的整除分块，不过只有60pts

8:20~9:20

T3似乎只会写前两档，写了个$O(n^{2}logm)$的循环卷积快速幂，顺便找了找规律，发现答案只会在n的质因子及其倍数的位置才会变化，因此猜一下T3是Pollard-Rho。

9:20~10:00

写了T2的暴力，发现了一些性质，但是感觉没啥用，后来写了个$O(nq)$的单调栈，不知道能不能有60.

10:00~11:30

发现T1可以之间利用调和级数的log暴力做，复杂度$O(nlnnlogn)$，不过树状数组常数很小，说不定能过，写了一下，测了极限数据发现跑的很快。

考后总结

T2

其实考场上想了一下个几乎一样的做法，也是线段树分治然后可持久化，只不过要写可持久化吉司机线段树，但是吉司机线段树是均摊的，因此不能做。
正解就是因为这个线段树只需要支持区间取max，全局求值，只需要写普通的线段树打标记就行了。

T3

非人类能达到的题