2022/03/22 做题记录

CF558E

字符集大小只有 26 ，于是可以对于每一个字符建一棵维护它出现位置的线段树，排序就是对 26 个字母分别区间求和然后依次区间赋值。

code: /code/2022.3.21/CF558E.cpp

模拟赛

A

赛时想到了奇数一次偶数一次分别加，但没想到怎么避免全 0 列带来的不连通。

事实上可以红色一次蓝色一次分别加，这样每一个不在第一行和最后一行的点都会与一个和自己颜色不同的点相邻，如果为 1 可以在加时一起加上，这样中间每一个点都会多加一次，而第一行和最后一行为 0 的点会多加一次，再减一次就行，因为中间有点在 $n \gt 2$ 一定能联通，而 $n \le 2$ 时答案一定小于等于 2（在交换完使得 $n \ge m$时。

对于答案为 0,1,2 的 dfs 找联通块即可。

code: /code/2022.3.22/bitbit.cpp