NOIP 2025 游记

最惊险刺激的一轮！

8:33 过 T1 没什么好说的，这比 CSP-S 还简单。

然后是 T2，转化为计算不合法的情况，发现只有在 $m$ 剩 $2$ 的时候选择了一个 $w_i=1$ 的时候才有可能不合法。

假设应该选 $a_k(w_k=2)$，实际选了 $a_i,a_j(w_i=w_j=1)$，那么就满足 $a_j+a_i\lt a_k\lt 2a_i$，枚举 $i,k$，$j$ 可以用双指针维护。此时容易做到 $n^3$。

发现式子可以用范德蒙恒等式优化，然后就做完了。说来也巧，这是集训时我出的那套模拟赛的 T2：

记得这个东西是初二的时候 tzy 讲给我的，印象很深，后来就试着给它出成题。当时赛时很多人直接用 $\log^2$ 卡过去啦，然后就没管正解，如今看还是有些遗憾的。

不过这玩意自己推应该也容易推出，所以我只是吐槽一下当时的情况，嘻。

总之 9:1x 过 T2。

然后看 T3，感觉是不可做题，跳了。

差不多 9:30 开始做 T4。

这里我用了个非常奇怪的方法，不知道有没有人和我一样，大概率是没有的？

看到这个东西我就发现 $q$ 比 $n$ 小很多，容易想到把询问的区间离散化，变成 $2q$ 个小段，我只要求出每个小段对于 $1\sim n$ 的答案最后离线用 $st$ 表之类统计一下就直接结束了！

令第 $i$ 个小段为 $[L_i,R_i]$，枚举左端点，直接先滑动窗口统计所有 $[j,j+L-1]$，剩下 $[j+L,\min(j+R-1,n)]$ 的长度为 $R_i-L_i+1$，考虑分块，比较好（？）维护。

差不多就是维护每个 $[j,j+B-1]$ 的和、前缀和的前缀 $\max$、前缀和的后缀 $\max$、右端点在 $[j,j+B-1]$ 中的 $[L,j-1]$ 最大值、包含 $[j,j+B-1]$ 的区间和最大值。

总之复杂度为 $n\sum_{i=1}^{cnt} \sqrt{len_i}$，$cnt$ 是分出的小段的数量，其中 $\sum_{i=1}^{cnt} len_i =n$，感觉就非！常！可行啊！

此时我通过了所有大样例（虽然我这种大常数选手可能直接被卡爆），但是我发现——空间炸啦！！！

因为我的算法要先存下一个 $2nq$ 的数组最后离线处理，但是%E&##的出题人 $|a_i|\le 10^5$，$sum\le 5\times 10^9$，$10^8$ 的 long long。

此时已经 11:45，我已经开始慌了，我发现我好像根本没有任何办法可以降低空间复杂度，T3 还没有写，我到底该怎么办？

所以，我直接摆啦！将 long long 直接换成 int。

然后我通过了所有大样例。

？

没错！此时我突然发现答案很难超出 int 范围！但是出题人肯定会有专门的数据卡，怎么办？欸！$sum\le 5\times 10^9$ 不就证明 $ans_{\max}-ans_{\min}\le5\times 10^9$ 吗？退一步讲，出题人真的可能出一个全 $10^9$ 且 $q=1$ 的狗屎数据来卡你吗？不可能！所以直接对每一个小段定一个偏移量，然后将记录的答案都平移到 int 里面！

咳咳，就这样，我在 11:50 的时候将空间卡进去了。

再来看 T3，一看就是个性质题或贪心。思考到 12:30 无正解思路，想出来的贪心都是一眼假，我是废物，直接打个 $n^3$ 和 $m\le 2$ 就滚了。

出考场发现 lwz 稳过 T124，%%%。xcx 因为只过了 T1T2 而没交代码？额，真不至于。好多选手没过 T2，个人感觉这次 T2 确实不太好的样子，长得跟个网赛似的，不过这些都是后话了。

最后得分 $100+100+56+[50,100]=[306,356]$，明年再来吧，滚回去学 whk 了。