RenaMoe's Blog

念念不忘，必有回响

0%

题解 LOJ#6500 「雅礼集训 2018 Day2」操作

发表于 分类于 ， Valine：

给出一串 01 序列和正整数 k，一次操作将长度为 k 的子区间取反，m 次询问一个区间内全部变为 0 的最小操作次数，不可能完成输出 -1。

\(1\le n\le 2\times 10^6,1\le m\le 5\times 10^5\)

很考验问题转化的题。

思路

暴力

原题 \(O(n^2)\) 暴力有 30 分，翻转策略是从左向右扫，遇到 1 就将以它为左端点且长为 k 的区间取反。

至于正确性，显然该位左侧的点不能再被取反。

运用差分（异或意义下）可以将区间取反降到 \(O(1)\)。

正解

观察差分序列，我们暴力中每次会把距离为 k 的两个点取反。

我们将询问区间提取出来，左右侧加上 0，再差分，观察：

原序列：0100011010

提取 [7, 9]：0 101 0

差分：01111

当 k 为 2 时，该例需要两步（即[7,8]、[8,9]）。

问题转化成在这样的差分序列中，每次将距离为 k 的两个点取反，需要的最小操作次数。

判断有解

可以得到，只有在编号模 k 值相同的位置中，1 的个数为偶数个，问题有解。

可以用哈希 \(O(1)\) 判断是否有解：

对编号模 k 值相同的位置赋一个 hash 值，然后对所有 1 做前缀异或和。

因为异或的性质，某个 hash 值有偶数个，异或起来为 0。

那么提取区间异或和即可判断是否有解。

计算答案

现在要计算最小操作次数，易得我们需要将编号模 k 值相同的位置中，所有的 1 相邻两两配对。

答案就是每对位置差除以 k。

我们还是对这些答案做前缀和，以便 \(O(1)\) 查询。

需要注意的是，两两配对的点中，做前缀和的话，如果有偶数个点那么恰好为答案；如果有奇数个点，要考虑到两个前缀和做差形成偶数个点的情况。

具体实现看预处理代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// b[] 模k值相同的位置的前缀答案
// sum[] 所有位置的前缀答案
for (int i = 1; i <= n; ++i) {
    sum[i] = sum[i-1];
    hsum[i] = hsum[i-1];
    if (a[i] ^ a[i-1]) {
        hsum[i] ^= hash[i%k];
        // 以下是重点
        sum[i] -= b[i%k];
        b[i%k] = i / k - b[i%k];
        sum[i] += b[i%k];
        // 如果有偶数个点，b[i%k]值为两两距离差除以k，即答案
        // 如果有奇数个点，b[i%k]值为i/k-原b[i%k]，即该位置减去之前的答案
        // 手模可以发现，这样子两个奇数点前缀和相减，配对情况恰好错开，值为新配对的答案
    }
    // 这里多记录两个值以便后续处理左右端点的影响
    bb[i] = b[i%k];
    br[i] = b[(i+1)%k];
}

左右端点的影响

因为提取区间要让区间左右侧为 0，前缀和中并没有考虑。

原序列：0100011010

提取 [7, 9] 的差分：

000000 1111 0

原序列 [7,9] 差分：

011001 0111 0

因为我们提取之后让区间左侧都变为 0，所以差分序列中第 7 位是不同的。

询问区间 \([l,r]\) 中，如果 l 处原来为 1，那么提取后的差分序列中该处一定为 1；同理，r 处为 1，那么差分序列中 r+1 处一定为 1。

其它地方的差分和预处理的就一样了。

那么就先通过预处理的计算 \([l+1,r]\) 的答案，再把端点的影响加进去。

因此预处理时要多记录当前答案状态，最后加入方法和预处理一样。

1
2
3
4
5
6
7
8
9
10
11
12
// bb[] 预处理中第i位的答案
// br[] 预处理中第i+1位的答案
int ans = sum[r] - sum[l];
int h = hsum[r] ^ hsum[l];
if (a[l]) {
    ans += bb[l] * 2 - l / k;
    h ^= hash[l%k];
}
if (a[r]) {
    ans += (r + 1) / k - 2 * br[r];
    h ^= hash[(r+1)%k];
}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <ctime>
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;

namespace RenaMoe {

template <typename TT> inline void read(TT &x) {}

const int N = 2e6 + 9;

int n, k, m;
int a[N], b[N], bb[N], br[N], hash[N], hsum[N], sum[N];
char s[N];

inline void main() {
    srand(time(0));
    read(n), read(k), read(m);
    scanf("%s", s+1);
    for (int i = 0; i < k; ++i) 
        hash[i] = (rand() % 32767 * 100000) + (rand() % 32767); // 这是什么辣鸡random方法啊
    for (int i = 1; i <= n; ++i) a[i] = s[i] == '1';
    for (int i = 1; i <= n; ++i) {
        sum[i] = sum[i-1];
        hsum[i] = hsum[i-1];
        if (a[i] ^ a[i-1]) {
            hsum[i] ^= hash[i%k];
            sum[i] -= b[i%k];
            b[i%k] = i / k - b[i%k];
            sum[i] += b[i%k];
        }
        bb[i] = b[i%k];
        br[i] = b[(i+1)%k];
    }
    int l, r;
    while (m--) {
        read(l), read(r);
        int ans = sum[r] - sum[l];
        int h = hsum[r] ^ hsum[l];
        if (a[l]) {
            ans += bb[l] * 2 - l / k;
            h ^= hash[l%k];
        }
        if (a[r]) {
            ans += (r + 1) / k - 2 * br[r];
            h ^= hash[(r+1)%k];
        }
        printf("%d\n", h ? -1 : ans);
    }
}
}

int main() {
    RenaMoe::main();
    return 0;
}