「Codeforces 1747D」Yet Another Problem - 构造 + 二分

发表于 分类于 ， 阅读次数： Disqus：

题意描述

Codeforces 链接

你有一个长度为 \(n (1 \le n \le 2 \times 10^5)\) 的整数序列 \(a\)。

你需要回答 \(q (1 \le q \le 2 \times 10^5)\) 个独立的问题，每次询问如下：

给定 \(l\) 和 \(r\)，你可以对序列做若干次操作（也可以不做），每次操作，你需要选择两个数 \(L\) 与 \(R\)，其中必须满足 \(l\le L\le R\le r\) 且 \(R-L+1\) 为奇数。然后将 \(a_L\sim a_R\) 的所有数改为 \(a_L\sim a_R\) 的异或和，即 \(a_L\oplus a_{L+1}\oplus \sim \oplus a_R\)。

你的目标是将 \(a_l\sim a_r\) 的所有数变为 \(0\)。每次询问完后，序列复原。

询问的答案即为最小操作数。如果总是不能达到目标，则答案为 \(-1\)。

解题思路

首先我们分析询问。通过异或的性质，我们很容易得出：在询问 \([l, r]\) 中，当 \(\oplus_{i = l}^{r}a_{i} \ne 0\) 时无解。否则会进行下列情况：

  • 当 \(\forall a_i = 0 (i \in [l, r])\) 时：显然操作数为 \(0\)。
  • 当 \(r - l + 1\) 为奇数时：此时只需要进行 \(l \rightarrow r\) 一次操作即可将整个区间变为 \(0\)，即操作数为 \(1\)。
  • 当 \(r - l + 1\) 为偶数时，需要分下列两种情况讨论：
    • 当 \(a_l = 0 \vee a_r = 0\) 时：去掉 \(a_l\) 或 \(a_r\) 可变为奇数情况，故操作数为 \(1\)。
    • 当该区间可被分为两个奇数长度的区间（且这两个区间的异或和均为 \(0\)）时：分别将这两个化为 \(0\)，显然操作数为 \(2\)。
    • 其余情况：由于只能选择奇数长度的段，于是无论如何都选择不出异或和为 \(0\) 的段，导致无法将区间化为 \(0\)。于是无解。

于是我们只需要预处理出异或前缀和 \(\text{res}\)，\(a_i\) 中 \(0\) 的个数 \(\text{cnt0}\) 和每个异或前缀和所对应的坐标集合 \(f_{0 / 1, m}\)（第一维中 \(0\) 表示偶数坐标，\(1\) 表示奇数坐标），然后查询即可。

  • 首先判断 \(\text{cnt0}_r - \text{cnt0}_{l - 1}\) 是否等于 \(r - l + 1\)。
  • 然后判断 \(\text{res}_{l - 1}\) 是否等于 \(\text{res}_{r}\)。
  • 当 \(r - l + 1\) 为奇数时：直接得出答案。
  • 当 \(r - l + 1\) 为偶数时：对 \(f_{l \bmod 2, \text{res}_{l - 1}}\) 二分求出大于 \(l\) 的最小坐标。若该坐标小于 \(r\)，则说明可将该区间分割，答案为 \(2\)，否则无解。

时间复杂度为 \(O(n \log n)\)。

代码演示

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
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>

int main() {
    int n, q;
    scanf("%d %d", &n, &q);

    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    std::vector<int> res(n + 1);
    for (int i = 1; i <= n; i++) res[i] = res[i - 1] ^ a[i];

    std::vector<int> cnt0(n + 1);
    for (int i = 1; i <= n; i++) cnt0[i] = cnt0[i - 1] + (a[i] == 0);

    std::map<int, std::vector<int>> f[2];
    for (int i = 1; i <= n; i++) f[i % 2][res[i]].push_back(i);

    while (q--) {
        int l, r;
        scanf("%d %d", &l, &r);

        if (cnt0[r] - cnt0[l - 1] == r - l + 1) puts("0");
        else if (res[l - 1] != res[r]) puts("-1");
        else if ((r - l + 1) % 2 || a[l] == 0 || a[r] == 0) puts("1");
        else {
            auto p = std::upper_bound(f[l % 2][res[l - 1]].begin(), f[l % 2][res[l - 1]].end(), l);
            if (p != f[l % 2][res[l - 1]].end() && *p < r) puts("2");
            else puts("-1");
        }
    }

    return 0;
}