NOI online 2021游记

今天打了打NOIonline，然后就身败名裂了

开场先看T1，想了个60的二项式定理+递推，感觉写起来有点麻烦

这时机房里所有人都说T2是简单题，就去看了T2，发现确实是简单题，在SAM的每个节点上记一下最大的长度，每次根据输入的字符转移就行了，而且自动去重。然后贺了个板子写了十几分钟过了大样例和群里的数据。

然后看T3，感觉非常可做啊，讨论一下b和d的大小，把询问拆成两个，和修改一起按照下标离线下来，每次上trie二分，相当于是要查询当前子树内比 (d) 大的 (b) 的个数，trie的节点上用set存一下子树内 (b) 有哪些感觉就行了。

写的时候发现set不能查询比某个数大的元素的个数，于是改成用vector离线下来每个节点做一遍动态开点线段树，空间仍然是 (n log n) 的。还有就是对于比 (d) 小的 (b) 可以用 (b) 来查询 (d) ，做两遍就行了。这东西写起来那叫一个折磨啊，还剩30min的时候才调完，当时点了提交就没管。

剩下的30min去写T1，结果没写完，也在意料之中。然后！在我交T1只过了第一个样例的代码的时候（这时还剩3分钟），发现T3代码没交上去，因为好像隔一段时间就要重新登录，~~CCF这十年前的网页还在用就nm离谱~~

当然还有时间，完全够我重新登录然后交T3，结果这服务器炸了...

可能就只有100分了吧，还好不是用的真名报的，不然肯定要被教练D

吃饭的时候交流了一下发现T2各种做法都能过，暴力+hash表去重，SA，好像就我写了个SAM。

考后上洛谷测了测，T2过了，T3不开O2只有20分，开了就过了。3.5h做一套（迫真）省选题还卡常，这是否有点