好好好有付费正式赛让你打你还不知足吗。
闲话重新开始更了，因为床上碰游记写差不多完了。
感觉为什么别人的游记写的内容都好多，但是一到我这里就少的不行呢???，可能是因为我在秦皇岛的时候写的吧???
先锐评下 csp2023：含原成分 50%，傻逼 CCF，希望别他妈 noip 也搞这随机选拔。挂分也挂够多了，T2 也想够久了，T3 不算特别难的大模拟没写，T4 再 CE 挂了 30pts。唯一值得骄傲的也就是 15min 切了 T1 吧???。
趣事：2023 春测、2023 省选 D1T1、NOI2023、CSP2023，挺有意思的。
妈的也不想说这傻逼比赛了，这里放出大 D 的一句经典：
无知时诋毁大 D，幻想中成为大 D。???
下午回到机房啥也不想干，妈的。但是 jimmy 让改题，还他妈的让我们写总结。最关键还他妈要发给他，这种东西难道不是自己游记里面写写就得了吗???
这里还是放出虚假的总结：
时间考试分配还算合理，T1 没花太多时间，T2 是原题，但是没做过，这里花了两个小时想 T2。T3T4 就没来得及写正解。主要问题是 T4 打完部分分没有编译就扔了。知识点方面这次考试没有考到任何知识点。以后提交代码前必须再重新编译一遍。
写的就很虚假???
啥也不想干，还困得要死。现在只想睡觉睡觉睡觉。
什么时候 HE 的 CSP-S 迷惑行为赶紧出来啊???，迫不及待了???。
没面基成功 HZOIer，也算遗憾了，看看 NOIP 能不能面上吧，到时候可能都成最后一次面基机会了???
为什么感觉没多少人写游记???
推歌：幻想浄瑠璃 -上海アリス幻樂団
CSP T2
给一种 \(O(n|\Sigma|)\) 且应该广为人知的做法。
我们定义一段字符合法（下称“消栈”）。设 \(f_i\) 为以 \(i\) 结尾的字符串有多少消栈，那么转移即为：
最终答案即为 \(\sum f_i\)。
现在的问题就是如何找到这个转移的位置。我们考虑一种暴力：我们从 \(i\) 往左扫，遇到相同数就弹栈，否则放入栈，什么时候栈空即为转移的位置。
这个玩意复杂度显然是 \(O(n^2)\) 的。但是我们发现如果两个相邻区间是消栈，那么它们拼起来也是消栈。我们就可以记录一个 \(pre_i\) 为满足 \(pre_i\sim i\) 为消栈的最大的 \(pre_i\)。还可以发现如果一段区间是消栈，那么两边同时加上字符 \(c\) 也为消栈。我们就可以一直跳 \(pre_i\)，直到找到前一位是 \(s_i\) 的位置，即可转移。
这样的复杂度我不清楚对不对，但是看上去像是 \(O(n^2)\) 的。
优化也很简单，我们可以稍微进行个路径压缩，记 \(pre_{i, c}\) 为从 \(i\) 开始跳 \(pre\)，第一个前一位为 \(c\) 的位置，这样转移可以做到 \(O(1)\) 转移。维护 \(pre\) 也很好维护，直接从前面 copy 过来，每次变化量也就只有 \(1\)，直接修改即可。
对于字符集更大的时候应该上主席树就行。
