CF1090H Linearization 位运算、前缀和

小灰灰 2021-11-26 09:42 230阅读 0赞

[传送门][Link 1]

--------------------

有点神仙的题目

首先注意到对于串\\(s\\)，\\(b=s\_0\\)一定会比\\(b = s\_0 \\bigoplus 1\\)更优

考虑先分析`linear`串的性质。注意到位运算考虑按位处理。我们考虑\\(x\\)的最高位，如果\\(x\\)的最高位为\\(1\\)，那么`linear`串的前后两半的异或和为\\(0\\)，否则前后两半完全相等。那么可以得到一个重要的性质：对于一个`linear`的串，把其分为前半段和后半段，前半段和后半段要么相等，要么完全不同，对于前后两半段还需递归满足这个条件。

好像有这个性质也没有什么用，但是注意到每一次的修改是区间取反，这在差分数组上会体现为两个位置的修改，比较方便。所以我们考虑差分处理。我们不妨分析一下差分之后`linear`串的性质。设\\(t\_i = s\_i \\bigoplus s\_\{i-1\} , i \\in \[1 , |s|)\\)。对于差分数组\\(t\\)，因为\\(s\\)的前半段和后半段相等，所以差分数组除了\\(\\frac\{|s|\}\{2\}\\)的位置可以随意取值，剩下的由\\(\\frac\{|s|\}\{2\}\\)分开的两个差分数组对应位置相等，且分开得到的两个差分数组还需递归满足这个性质。

我们对于给出的\\(01\\)串进行差分，对于一个询问\\(\[l,r\]\\)只需要将\\(\[l+1,r\]\\)的差分数组用尽可能少的单点取反变为一个满足`linear`串差分数组性质的数组。注意到`linear`串差分数组的性质是一些位置的值相等，我们可以把这些值拿出来，用\\(\\min\\\{cnt\_0 , cnt\_1\\\}\\)贡献答案，这样可以做到\\(O(nq)\\)。

最后需要考虑如何快速求出一个连通块内\\(0/1\\)个数。不难发现对于所有\\(lowbit\\)相等的位置会形成一个连通块（这个可以考虑所有\\(lowbit\\)相同的点，然后考虑自底向上时的连边情况，不难发现这些点连成一棵树且没有往外连边），然后记一下前缀和计算对于\\(lowbit\\)相等的所有位置的\\(1\\)的个数即可。

[代码][Link 2]

转载于:https://www.cnblogs.com/Itst/p/11135227.html

[Link 1]: https://codeforc.es/problemset/problem/1090/H
[Link 2]: https://codeforces.com/contest/1090/submission/56514185