代码见 3/6(牛客)，NUAA01(杭电) 或 洛谷剪贴板
今年多校是和 atom(AtomFirst) 和 hlgg(hubbya) 一起打的。
牛客多校 Day 1
火速开签到，atom 发现 G 只要暴力求出匹配再统计一遍答案就行了，上来就切了。
然后和 hlgg 看 E，手玩发现平方数的差可以生成以 \(3\) 开头的奇数数列和以 \(8\) 开头的 \(4\) 的倍数数列，并且平方差要么为奇数，要么模 \(4\) 为 \(0\)，所以就做完了。我上机写完交了一发 WA 了，马上发现爆 int，改了就过了。
继续和 hlgg 看 L，发现中位数总是不降的，所以可以直接维护中位数！跟 hlgg 讲了这个思路就让 hlgg 上机写了。
接下来和 atom 一起看 K，发现如果把每个门作为状态的话就是一个基环树森林，可以找到环转移。但是因为走廊可以重复走，并不是很会计数走廊个数。后来 atom 思考了一下发现根本没有基环树！全是环！我随即上机写写写就过了。
这中间 hlgg 写了一半的 L 发现不是很好写，所以我上机重新写了一遍 L。交上去发现 T 了，非常神奇，原来没删 std::cerr，再交发现 WA 了。旋即发现用 %d 输出的 long long，我突然释怀地笑，然后交上去又 WA 了，后来发现不是这个问题，因为答案本来就不会爆 int，但是有一处 int 没改成 long long，改了交上去还是 WA /kel。hlgg 想了一会发现我维护 mid 时处理小于 mid 的数的更新逻辑有一点问题，我思考了发现很有道理，改了终于过了！这题确实不是很好写！
大家一起看 H，操作 1 可以用差分数组 \(O(1)\) 维护，然后操作 2 可以用 G 的做法 \(O(n)\) 暴力查询，这样总复杂度是 \(O(q_1 + n q_2)\)。开了 4s 我比较有自信能跑 \(nq_2 = 2.5 \times 10^9\)。但是这个做法太暴力了，而且这道题 dirty 率非常高，所以肯定不是正解，尝试让 atom 写了一下发现果然 T 了。大力卡了一下常还是 T，所以就放弃去看 I 了（赛时确实放了个别暴力过去了，赛后这题的时限改成了 2s，感觉这道题出得没那么好）（lxl：数据结构的本质是卡常）
I，先和 atom 胡了一下 \(O(n^4)\) 的区间 dp，状态数只有 \(O(n^3)\)，但是转移需要 \(O(n)\)，所以接下来就是怎么考虑优化转移。我和 hlgg 一直认为要求的 \(\min \times \log\) 一定有某种意味，于是猜了个每次转移只要考虑不平衡度最大的合法区间的结论。结果 atom 这时自己想出来了可以维护最优转移的方法，直接上机开写。接下来全程端茶送水，并不是很懂 atom 的做法，封榜后一直在摸鱼，而 hlgg 帮 atom 调了很多。I 先是 WA 然后 T，我建议把 std::map 换了，atom 改了发现没改对，在最后的紧要关头，发现 upper_bound 写错了，最后 3min 提交过了，没 WA 也没 T。那我只能拜谢 /bx。看了题解后大家锐评 \(\min \times \log\) 的意义就是让你 TLE 的。
第一场感觉打得不错，n+1 了残阵的 loveless。
H 暴力是 \(O(q_1 + nq_2)\) 的，因为是 01 串，考虑手写 bitset 分块处理，设块长为 \(B=16\)，对于操作 1 仍然维护差分数组，对于操作 2 只要处理 \(O(\frac{n}{B})\) 个块（可用 unsigned short 提取），接下来考虑 \(O(1)\) 合并两个块需要维护哪些信息。首先是块内贡献，然后只要知道前缀零和后缀零个数即可合并，因为块的状态数只有 \(O(2^B)\) 种，可以 \(O(B2^B)\) 预处理。
I 设状态为 \((l,r,m)\) 表示区间 \([l,r]\) 在 \(m\) 进行分隔，可以算出不平衡度，处理 \([l,m]\) 和 \([m+1,r]\) 各自关于不平衡度的前缀对应的代价最小值就可以二分 \(O(\log n)\) 转移最小代价。 要做到 \(O(1)\) 转移，需要注意不平衡度在中心点向两边是递增的，所以可以直接求前缀最小代价，并且向左右转移的时候类似地也从各自中心点进行转移。空间开 \(n^3\) 的long long 数组发现直接爆炸了！但是因为 \(l,m,r\) 有顺序所以可以数组只开 \(\binom n 3\) 约为 \(\frac{n^3}{6}\) 大小。