2023/11/29(#2)：每当我为你抬起头，连眼泪都觉得自由

有的爱像大雨滂沱，却依然相信彩虹

我可以跟在你身后
像影子追着光梦游
我可以等在这路口
不管你会不会经过
每当我为你抬起头
连眼泪都觉得自由
有的爱像大雨滂沱
却依然相信彩虹
相信彩虹

张杰这一版唱出了光的感觉，太感动了！！

大意了，模拟赛 T2 没有测奇数的数据！

怎么还是只会做简单题！

我怎么还断更了一天（所以今天实际上是两天的素材，我太摆了）！

[Luogu P5351] Ruri Loves Maschera

Portal.

点分治，统计信息时记录 $d$ 和最大值 $w$，扫描线扫 $w$，树状数组维护 $d$ 即可。代码。

[CF960H] Santa’s Gift

Portal.

一开始读成了撒旦的礼物。

将贡献拆了，发现问题变成了维护子树中每个颜色的个数。由于总共能出现的颜色只有 $O(n+q)$，因此直接每个颜色都建一棵支持区间加的动态开点线段树维护即可。代码。

[ARC102D] Revenge of BBuBBBlesort!

Portal.

迄今为止我到底见到了多少冒泡排序复仇题！

思考一下交换意味着什么。一次交换废掉了三个逆序对，因此逆序对个数是三的倍数是必要条件之一。

然后交换时数的奇偶性是不变的，因此奇数只能在奇数位，偶数只能在偶数位。

于是不难想到把奇数位和偶数位分为两组，每次可以废掉奇数序列或者偶数序列的一个逆序对。这样看来，整个序列的逆序对个数应该是奇数序列逆序对加偶数序列逆序对的三倍。

一个操作合法当且仅当其能消除三个全局逆序对，而且一次操作最多消除三个全局逆序对，因此这个东西充分。代码。

[NOI Online 2022 提高组] 如何正确地排序

Portal.

我们考虑计算对 $\min,\max$ 没有贡献的数，枚举三个数组 $A,B,C$，如果 $B$ 没有贡献，那么应该满足 $A_i+A_j\le B_i+B_j\le C_i+C_j$。移项之后变成二维偏序，直接做，注意防止算重。代码。

[Ynoi E2022] TEST_105

Portal.

不会做套路题怎么办？？套路没见过怎么办？？还疯狂摆烂怎么办？？

首先，树上邻域信息一定只能维护子树的信息，否则单点修改会导致所有儿子都需要修改，复杂度直接爆炸。

令 $C_{i,j}$ 表示 $i$ 点所在子树范围内的连通块的 $j$ 色连通块序列，修改时直接启发式合并，只需要更新 $C_{fa_x,y}$ 即可。

为什么中途还写挂了啊？？？？还调了半天？？？？？？

「C.E.L.U-03」探险者笔记 III

Portal.

两个和式就是唬人的，因为它们是定值，暴力转移就是 $O(m^2)$ 的。然后发现第三维可以直接暴力枚举子集处理。

但是这样显然不对。修改时有两种想法，将 $p_j$ 存下来，枚举 $p_i$ 的子集；或者处理 $p_j$ 的超集，$p_i$ 直接计算。将 $18$ 位二进制数劈成两半，定义 $g_{s,t}$ 表示 $p_i$ 前 $9$ 位为 $s$，$p_j$ 后 $9$ 位为 $t$ 的最优决策即可完成平衡。代码。

ED

下午干一些比较重要的事情。