比赛链接: https://acm.ayit.edu.cn/contest/11

A: A*B Problem

题如其名, 直接取a*b输出即可

不知道为什么的请复习小学数学

标算代码: https://acm.ayit.edu.cn/submission/3459

B: 混乱的排列

所有数字不相同的情况构造成两段单调区间就能做出0~n-1的所有情况了

有相同数字的情况下, 按mx->mn,mx->mn...的方式反复选取可以得到最大混乱度

形式上类似3 2 1 3 2 1 3 2 1这样

然后我们扫描这个构造好的数列, 取混乱度达到m的位置i并对i~n排一次序即可

标算代码: https://acm.ayit.edu.cn/submission/3465

C: 次方数

子任务1: 我会写暴力!

子任务2: 我还是会写暴力! 显然有意义的范围内 z < 63 , pow验证即可

子任务3: 取10^6内的所有数x, 跑出所有x^z放进一个哈希表里

对于一次查询不在表中的结果显然是x^2且 $x>10^6$ ,开个方特判即可

标算代码: https://acm.ayit.edu.cn/submission/3466

PS: 我的标算长得有点奇怪? 因为这题本来还有些限制条件, 不过后来被我砍了

D: 不下降子串

考虑查询的本质是什么, 稍作思考就会发现其实是统计区间内的 A[i] > A[i+1] 数量

那就是统计区间内差值为正的位置的数量

而一次区间修改并不会改变区间内的差值, 只会改变两个端点附近的差值

好了, 扔个树状数组维护区间和, 没了

标算代码: https://acm.ayit.edu.cn/submission/3469

E: 能量环

子任务1: 很明显的可以看出来就是矩阵快速幂, 扔板子, 没了, 复杂度 $O(Tn^3logQ)$

子任务2: 针对同一种矩阵转移的多次查询? 预处理k进制矩阵快速幂, 没了, 复杂度 $O(Tn^3S + Sn^3\sqrt[S]Q)$

什么没了, 你数据造小了被普通矩阵快速幂跑过去了, 太sb了

子任务3: 这个n有点大, 怎么办?

注意到给定的转移矩阵是一个循环矩阵, 而循环矩阵和循环矩阵相乘后仍然是循环矩阵

所以我们只维护矩阵的第一行就能还原出整个矩阵了, 矩乘的复杂度也降到了 $O(n^2)$

总时间复杂度 $O(Tn^2S + + Sn^2\sqrt[S]Q)$

标算代码: https://acm.ayit.edu.cn/submission/3470 (代码中S的取值为4)

F: 子树的最值

子任务1: 设f[i][j]表示i的子树内所有深度为j的位置的点的权值和

树归一次后求出前缀和即可得出答案, 复杂度 $O(n^2)$

子任务2: 由于是一条链, 我们可以当做一个序列来做

考虑如何维护信息, 我们在任一个点都需要维护其整个子树的权值前缀和

考虑从叶向根扫描, 用线段树维护前缀和, 操作上单点修改变成后缀式修改即可

线段树维护区间最值大家应该都会, 那这部分就解决了, 复杂度 $O(nlogn)$

什么你还是不会做? 从线段树根向叶子走, 每次优先走左边, 左边对应的查询区间中不包含满足条件的值才往右走就行

当然如果整个区间的最小值都 $>=B[i]$ 那答案就是 $-1$ 啦

子任务3: 我们已经会在链上做了, 现在考虑怎么跑到树上做

不带修的关于子树内的深度相关信息的维护? 长链剖分呗

将整棵树按照长链剖分, 每条长链用一棵线段树维护信息, 合并也是显然的.

注意要先扫描长链再扫描其他链, 否则信息会提前合并影响查询

复杂度 $O(nlogn)$

标算代码: https://acm.ayit.edu.cn/submission/3472

吐槽环节:

你看这个F就是水啦

太逊了, 整场都水爆了

蜜汁观众: 所以E的子任务2的查询为什么不开到 $3 * 10^5$

因为弱智出题人写错了范围然后数据传上去懒得改了

怪我怪我orz...

蜜汁观众2: 所以C的最后一组数据为啥是 $5 * 10^4$

wc

弱智出题人又一次写小了范围, 怪我怪我orz...

怎么还有对压缩后的序列直接插值的啊, 我本意真的只是压缩下输出文件啊