2025 noip 游记喵

在家，tetr.io 打到了 4k 分，机心无敌了。

诶我怎么有点感冒？

诶我怎么有点发烧？

算了不管了先考试吧

开题，t1 是个签，考虑哪个会选超过 1 次即可，1 min 会了，写写写，饶是如此我依旧写了 20min。

开 t2，数数题？？？？？？我不会啊，跳了。

开 t3，一开始读错题了以为要求整棵树 mex，仔细读题之后发现不会，跳了。

开 t4，一眼出了一个 $O(n(R-L)+nq\log n)$ 的离线分治做法，空间是 $O(nq)$ 的，应该有一点点分，中途电脑莫名其妙死机了，获得加时。

大样例跑了 $16s$，卡不过去 qnq。

发现特殊性质都跑的挺快的，应该是有剪枝的缘故罢。

t4 预处理的的滑动窗口拆下贡献应该可以做到 $O(nq\log n)$，还有 2h，不一定写得完写完也不一定跑得过，先去看 t2。

感觉加一个 0 之后不合法状态一定前面任意中间一个 1 然后一些 2 然后又一个 1，调整方法去掉两头的 1 然后选中间的 2。

于是就可以枚举两头的值为 $a_x$ 和 $a_y$，分别维护第一个大于等于 $2a_x$ 和 $a_x+a_y+1$ 的值，然后考虑一个组合意义：

显然是到左边的 $2a_x$ 之前的数选 $t$ 的话对前缀代价有 $t$ 的贡献，$2a_x-1$ 到 $a_x+a_y+1$ 中必须取一个 $2$ 在 $a_x$ 到 $a_y$ 性价比区间里成为被调整的数，剩下的取什么贡献和下面一样，$a_x$ 到 $a_x+a_y$ 中的数选 $2$ 则有 $0$ 的前缀贡献，选 $1$ 则有 $1$ 的前缀贡献。

而 $a_y$ 到 $a_x$ 这段区间已经被确定（中间的数必须全选 $2$ 保证他们俩性价比区间中只有 $1$），$<a_y$ 的可以任意取，于是两个组合数的差乘一个二的幂求和即是答案。

推出了这样一个有四个系数的组合式子，还可以平方计算，应该是正解了，然后调调调，发现小样例过了，大样例死活过不去，诶 wc 没时间了。

再见 oi，希望你我喜欢这 $7$ 年来属于你的戏份。

甲流我*****，为什么非得当天发作啊。