Yet Another Problem

Created by LXC on Wed Jan 10 13:36:29 2024

https://codeforces.com/problemset/problem/1747/D

ranting: 1900

tag: binary search, bitmasks, constructive algorithms, data structures

problem

你有一个长度为 $n$ 的整数序列 $a$。

你需要回答 $q$ 个独立的问题，每次询问如下：

给定 $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$。

solution

猜结论。

对于[l,r]如果异或和不为0，那么无法通过操作变为0。

排除以上情况，对于全为0的串，无需操作。

排除以上情况，对于奇数长度的串，只需一次操作。

排除以上情况，对于偶数长度的串，可以拆分成两个奇数长度的串。 如果这个串开头或结尾是0，那么只需要一次操作。否则我们需要找到一个奇数长度的前缀异或为0的串。这个可以通过预处理将相同前缀异或值的下标并区分奇偶性纳入同一数组，然后二分得到。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;


void sol() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n+1), s(n+1);
    vector<ll> z(n+1);
    map<int,vector<int>> mpo,mpe;
    mpe[0].push_back(0);
    for (int i=1; i<=n; i++) {
        cin >> a[i];
        z[i] = z[i-1] + a[i];
        s[i] = s[i-1]^a[i];
        if (i%2) mpo[s[i]].push_back(i);
        else mpe[s[i]].push_back(i);
    }
    while (q--) {
        int x, y;
        cin >> x >> y;
        if (z[y] == z[x-1]) { // 全0无需修改
            cout << "0\n";
        } else if (s[y] != s[x-1]) { // 串异或为0
            cout << "-1\n";
        } else if ((y-x+1)%2) { // 奇数长度
            cout << "1\n";
        } else if (a[x] == 0 && s[y] == s[x] || a[y] == 0 && s[y-1] == s[x-1]) { // 偶数长度，存在0前缀或后缀
            cout << "1\n";
        } else {
            auto& t = (x%2?mpo[s[y]]:mpe[s[y]]);
            int l = upper_bound(t.begin(), t.end(), x-1) - t.begin();
            int r = lower_bound(t.begin(), t.end(), y) - t.begin();
            // cout << l << " " << r << endl;
            if (l<r) {
                cout << "2\n";
            } else {
                cout << "-1\n";
            }
        }
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}