2022/3/11 考试总结

赛时安排

7:40~8:00

看完题，发现T3是原题
依稀记得是多项式加速第一类斯特林数
保险起见先写写了个暴力求第一类斯特林数
一下就过了样例
因为有前车之鉴，所以不敢去写多项式，先去看前两题了

8:00~8:20

T2的$k\le 3$很奇怪
$k=1,k=2$都很好做
但是3就没有什么性质
推了一下，发现对于一个左端点，连续区间按位与的变化是$O(log{a}_i)$级别的
因为每一位如果变成0就不会变了
可以对每一个二进制位开个桶，在桶里二分找后面第一个会使得当前为从1变成0的位置
然后这样的区间个数是$O(n\log a)$的
然后查询的时候，把询问离线，用一颗线段树维护就行了
然后就赶紧写

8:30~9:00

写T2

9:00~9:40

写完之后，码了个暴力对拍
正确率没什么问题，但是常数很大，跑了2.3s
加上快读，把线段树改成树状数组，发现只跑了1.7s
但是还是有被卡的风险的
测试了一下发现是输出竟然输了800ms
改成快写，就跑进1s以内了

9:40~10:10

T1没有思路，写了个$O(n{m}^2)$的做法就弃了
期望得分45pts

10:10~11:15

快速回忆了一下如何求第一类斯特林数
似乎只需要一个NTT和一个倍增
就赶紧码，码完拍一下，然后再卡卡常，应该问题不大

11:15~11:50

检查，对拍

订题总结

T1
其实本质是离线扫描线，只不过是把不断加入，变成不断删除
但是，还是第一次见到把trie树的儿子合并起来这种操作
然后再启发式合并维护
感觉挺妙的
T2T3的思路都和题解是一样的