NOI Online2022游记
热度: loading...
很遗憾，虽然蒟蒻的游记没写完也没人看，但打完noio后下午状态不佳，直播打2019联合省选也一道题都没打出来。遂滚回来写游记。
7:30闹钟响，但是昨晚补题补到比较晚，没被叫醒，睡到8：30起床。
起床一看8:30也不着急（以为比赛4.5h），吃完早饭后开题，此时9:00
开T1，一眼看到题名：单调栈，然后开始看题面。题面确实是一个栈，开始想暴力。一眼看去只有 暴力，想了想 的暴力，但怎么也想不出来。遂开始想正解。
9:16 对着题面盯了一会，想到每个元素只会被固定的一个元素挡住，联系题面单调栈，想到用单调栈预处理每个元素被挡住的位置，只要这个元素在区间内，且能挡住这个元素的位置在区间外，这个元素就能把栈底全部弹掉，产生贡献。
设能挡住第 个元素的位置是 ，则问题变成了统计 且 的所有点，将每个元素看成坐标为 的一个点，这变成了一个二维数点问题。想到二维数点于是想到用主席树维护，开始写代码。
10:00 写完并调完代码，前三个样例正常，第四个样例虽然过了但是本机耗时 3.8s ，感觉有点慌，一想主席树的复杂度是 而 都是 级别，整个复杂度是 级别，感觉被卡掉也是有可能的，保守估计估了个50pt，看了下剩余的部分分，感觉不太会做。
看了眼结束时间，发现只有3.5h，吓了一跳。
10:00 11:00 打了T2，T3的暴力。T3的 部分观察了下发现最大值和最小值一定包含了两行的所有部分，答案就是 。
11:00 继续滚回来想T1，看到 的部分分，发现只用考虑 ，且答案为 内最长前缀相同 串。于是想到个做法：把所有 相同的串缩起来，于是答案可以直接二分相同 段，于是复杂度变成了 （少了个 ）。感觉可过。打完之后时间到 11:30 。此时估分 。
11:30 之后继续想，考虑继续优化T1。看到群上有人谈到树状数组，于是开始想怎么用树状数组替代主席树。想了想决定把询问差分到数组上来统计答案（其实这样想想普通的权值线段树加个差分也可以，我去打什么主席树）。11:50分打完，感觉会快很多，但测了下速度大概是 3.4s ，只比主席树快了0.4s。好在之后把数据放到 OJ 上测了一波，第四个点只要 200ms，遂安心摆烂。
11:50 12:00 试图用STL自带的交集工具优化T2，但是没写完。
赛后用洛谷民间数据测了下： ，感觉没到大众分，滚回去摆烂了。
顺便 %% zyf
2022/3/20 upd: T1的正解居然就是 ，浪费我1h时间。
