前言 & 闲话
比赛质量还行，但是出了很多搞笑的状况，比如 T3 的空间莫名其妙变成了 2048MB，大概是4点多吧，反正我打的时候准备看 T3 的时候来了个提示说 T3 空间限制修改了。
莫名其妙，而且有一个比较好玩的情节。
不会重复提及某题题意，请自行观看。
T1
红，没什么好说的，注意一张饼需要操作 kkk 次，同时有 nknknk 面需要操作，答案就是 max(k,⌈nkm⌉)\max (k,\lceil \frac{nk}{m}\rceil)max(k,⌈mnk ⌉)。
懒得给代码。
T2
构造可能有点创人，但是我觉得还好。这个扩展有一个特性：加入一个格子水域周长不会增多。原因很显然，因为规则中指出格子四联通周围有两格及以上才会扩展，一个格子就四边。最好的情况相当于有两面接壤，然后有两面补上了原来接壤的那个空缺，周长不变。
然后我们发现最终状态整个网格都被填满，水域边长为 2nm2nm2nm。也就是说答案的下界一定是 ⌈n+m2⌉\lceil \frac{n+m}{2} \rceil⌈2n+m ⌉，相当于一个格子周长为 444。下界也不难得到，构造如下：
* 在左上角 2×22 \times 22×2 上方的 (1,2)(1,2)(1,2) 和 (2,1)(2,1)(2,1) 放水，把这块区域填满。（出题人巧思不错，这就是 MC 里面无限水的做法）
* 然后我们发现可以隔着两个放一桶，比如填满列就填充 (1,4),(1,6),(1,8).....(1,4),(1,6),(1,8).....(1,4),(1,6),(1,8).....，这样我们可以让第一行都被填满，第一列同理。
* 然后我们发现此时整个过程相当于说逐渐从边缘扩展，逐步的水会扩展每个格子。
还有一些特殊情况，这样的方案无法覆盖到末短是奇数格子的情况。比如 nnn 为奇数时，格 (n,1)(n,1)(n,1) 就无法被覆盖到，此时加进去就可以了，如果 mmm 是奇数同理。需要注意的是，当 n，mn，mn，m 均为奇数时只需要填充 (n,m)(n,m)(n,m) 即可，不然会有冗余。从这里也可以看出构造是严格达到下界的。
时间复杂度 O(nm)O(nm)O(nm)，总体而言还行。
这是这位同学你 @消失的AC与写不完的UKE 要的代码。
下次记得晚点发hhh。
T3
有点意思，这是一个比较新颖的题，但其实也比较简单。首先其他数出现两次这个性质启示我们想办法对这些数作区分，一个运算能很好的体现这个区分性：异或。
因为 x⊕x=0x \oplus x = 0x⊕x=0，原序列的异或和就是要求的那两个数 x,yx,yx,y 的异或值 sum=x⊕ysum=x \oplus ysum=x⊕y。并且我们发现 sumsumsum 至少有一位非零，因为 x<yx<yx<y。然后此刻某一位为 111 的意思就是这两个数二进制下这一位不同，随便找到一个为 111 的位，如果 d=2d=2d=2 针对这一位为 111 的再做异或就可以得到 x,yx,yx,y 的某一个，然后再和 sumsumsum 异或一次就得到两组解了。
到正解其实和 d=2d=2d=2 没什么区别，二进制位一共就 logV=60\log V = 60logV=60 位左右，每次读入的时候开一个大小为 606060 的数组 pip_ipi 表示第 iii 位为 111 的所有数的异或和，然后直接查表就可以了。
时间复杂度 O(nlogV)O(n \log V)O(nlogV)，空间复杂度 O(logV)O(\log V)O(logV)。当时是写了个模拟过的（2G空间），后面觉得有点不地道然后写了个正解，反正场上两种都过了。
T4
思考了 10 分钟，有一个细节有点意思，其他没什么难度。
首先一个经典的观察是每个数最多经历过 loglogV\log \log VloglogV 次开根操作就变成 111 了，所以这一部分是可以对每个数暴力做的。然后观察数变成 111 后的特殊性质：
* 如果目前操作是 +1+1+1，那开根后向下取整还是 111。
* 如果目前操作是 −1-1−1，那直接就是 000。
同时，000 怎么操作都一定会变成 111，所以每个数最终的归宿 000 或 111 可以批量维护，我们只在意个数。如果操作是 +1+1+1 就没影响，否则就交换 000 和 111 的个数。查询就是 111 的个数加上其他数的和。
重点是合并操作，由于这个 nnn 太大了不能直接启发式合并，但其实有一个很聪明的方法规避暴力合并：使用链表维护所有大于 111 的数，再做合并。（开头提到的有点意思的点）
链表合并的方式很简单，记录链表的头指针和尾指针，合并时把一边的尾指针的后继改成一边的头指针就行了。这个过程时间复杂度是 O(1)O(1)O(1) 的，然后很经典的用并查集维护集合。
处理开根操作的时候遍历链表，每个数暴力处理，更新总和并且看看操作后能否规约到 0/10/10/1。这一点可以使用两个变量维护头指针和尾指针，具体实现看代码，没什么好说的。
开根反而是时限瓶颈，这里卡常使用了一个值域分治技巧，如果数 ≤107\le 10^7≤107 查表即可，这一点可以简单预处理。默认开根为 O(1)O(1)O(1) 则总时间复杂度为 O(nloglogV+qα(n))O(n \log \log V+q\alpha(n))O(nloglogV+qα(n))。
