2022.7.18 模拟赛题解

草莓蛋糕

赛时写了两个 log 的线段树分治+平衡树上二分的做法，没有前途（毕竟线段树分治就一个 log 了，O(1) 计算不太可能）。

“时间分治不了就序列分治”

但有个 max，不太好合并两边的贡献。

发现 $a_c+b_c>a_y+b_y$ 等价于 $a_c-a_y>b_y-b_c$。

于是设 a 类的权值为 $a_c-a_y$，b 类的权值为 $b_y-b_c$，这样通过权值的大小就可以知道贡献取哪边。

可以将原序列按照权值排序，这样统计来自两个分治区间的贡献十分容易（因为如果知道哪边选 a 哪边选 b 贡献取什么可以确定，只需要分别维护 $a_c,b_c,a_y,b_y$ 的最小值）。

线段树维护即可。

code: http://47.92.197.167:5283/submission/102034

矩阵补全

FWT 实际上就是把每个数替换成一个满足某个条件的集合的和，这样按位乘起来就相当于在这两个集合中任选一个数，而 iFWT 就是将这些乘积放回到对应的位置上去，于是 FWT 实际上是可以给每一位进行不同的操作的（或，异或，与），可以认为在对这一位进行操作的时候所有高位的影响已经排除，只按这一位操作就能达到期望的结果。