Codeforces Round #741 D2(1562D2) - Two Hundred Twenty One (hard version) 题解

一种比官方题解简单一点的做法

前置知识 #

确保你已经知道 D1 的做法

题解 #

由于我们已经知道了区间长度为偶数的时候最多只用去掉两个数而长度为奇数的时候要去掉一个数，所以对于区间长度为偶数的询问，我们可以去掉最后一个数从而将其转化为长度为奇数的询问，所以我们只要考虑如何求长度为奇数的询问即可。

首先还是像 D1 一样求出前缀和，将 $l\dots r$ 的区间和记作 $S_{l, r}$ 。不难得出去掉一个数之后区间和会变成 $S_{l, i-1}-S_{i+1, r}$ 。我们想使其为 0，所以要找到一个 $i$ 使得 $S_{l, i-1}=S_{i+1, r}$ 。将等式做如下变换：

\begin{align*} S_{l, i-1}&=S_{i+1, r}\\\ S_{0, i-1}-S_{0, l-1} &= S_{0, r} - S_{0, i}\\\ S_{0, i-1} + S_{0, i} &= S_{0, r} + S_{0, l-1} \end{align*}

所以我们可以提用所有 $i$ 的 $S_{0, i-1}+S_{0, i}$ 的值构建反查表（即给出 $S_{0, i-1}+S_{0, i}$ 的值查询符合条件的 $i$ ）。这样就可以做到 $O(\log n)$ 回答询问了（log 来自于在反查表中二分）。

代码 #

#include <bits/stdc++.h>
using namespace std;
 
void test_case() {
    int n, q;
    string s;
    cin >> n >> q >> s;
    vector<int> ps(n + 1);
    vector<vector<int>> pos(4 * n + 1);
    for (int i = 0; i < n; i++) {
        int x = (s[i] == '+' ? 1 : -1);
        ps[i + 1] = ps[i] + (i % 2 ? -x : x);
    }
    const int OFFSET = 2 * n;
    for (int i = 1; i <= n; i++) {
        pos[ps[i] + ps[i - 1] + OFFSET].push_back(i);
    }
 
    auto solve = [&](int l, int r) {
        int x = ps[l] + ps[r] + OFFSET;
        auto it = lower_bound(pos[x].begin(), pos[x].end(), l + 1);
        assert(it != end(pos[x]) && *it <= r);
        return *it;
    };
    while (q--) {
        int l, r;
        cin >> l >> r;
        l--;
        if (ps[r] - ps[l] == 0) {
            cout << "0\n";
        } else {
            if ((r - l) % 2) cout << "1\n";
            else cout << "2\n" << r-- << ' ';
            cout << solve(l, r) << '\n';
        }
    }
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt = 1;
    cin >> tt;
    while (tt--) {
        test_case();
    }
}