2025 炼石计划 梦熊模拟赛 记录
#1
总结
T1难难难难难。
T2T3唐爆了，（几乎）过了。
分数：0+90+（90）=180。
T1
怎么这么难，harddddd。
考虑找到连通块的直径的中心，然后奇偶分讨一下。
考虑奇数时，有唯一中心，如果唯一中心合法，那么唯一中心的所有全为黑点的子树一定合法。
考场上想到这里就停了，当然到这里都比较简单，但是比较难写，不像正解。
后来发现可以维护，而且这还是正解？
具体来说有点难写，发现按照空集作为断点将询问分段，每段内中心的移动是 \(O(len)\) 的，可以线段树维护距离。
T2
签到题。考虑排序之后一定是左右-m,+m，然后中间去凑，发现可以线段树维护。
哦对了，不开 int128 只有 90 分。
T3
为什么省选模拟只有四个半小时？赛时未提交。。
手推出了双调排序。考虑如果左右两个序列等长且已排序，那么可以翻转右边，然后让左边取 \(\min(a_{l+i},a_{mid+1+i})\)，右边取 \(\max(a_{l+i},a_{mid+1+i})\) 发现左右的值域会变得不交，可以分别排序，感觉就很对。
进一步观察发现，左右分别变成单峰序列和单谷序列。那么我们考虑处理单峰序列的排序（单峰函数可以由单谷函数循环位移得到）。发现同样可以左边取 \(\min\) 右边取 \(\max\)，同样是值域不交的。但是会有一个序列可能变成三折叠，但是可以循环位移变成单峰。
优化一下常数，把交换当成交换指针，然后询问时询问指针指向的位置，那么可以在过程中省掉交换最后来做。
到这里的询问次数，手算出来应该是 200+ 次，然后在最后指针归位时，由于来不及了所以写了个快速排序，可以过掉 90 分。
赛后经过 BIN 哥提醒，可以直接从排列的置换环入手，把置换环切一下，就可以一次交换使得只剩下二元环，一次交换全部归位。总的次数是 212 次。
#2
总结
怎么 T1 又 harddddd，还是我菜了？
T2 有点东西，但不多。T3 感觉快会了，但在 T1 上浪费了很多时间，只写了 40 分暴力。
分数：0+100+40=140
T1（未改）
不会，可能是前两个01出现次数有关？推出一大堆没用的性质分，果然推性质之前得先看部分分要求。
T2
考虑从最终局面倒着做，第 n 个盘子一定不动，因此最终局面时所有盘子摞在第 n 个盘子的柱子上。
那么倒着扫一遍，如果1到i的盘子当前在第 u 个柱子，i 应该放在第 v 个柱子，那么：如果 u=v 显然可以不移动，无贡献；否则将1到i-1这些盘子移到 第 6-u-v 个柱子上，然后把 i 移到第 v 个柱子上，花费 \(2^{i-1}\) 次操作。
那么这个显然可以线段树维护。
T3（未改）
只会 40 分。哭了。