CF1896D Ones and Twos 题解

wxzzzz · 2024-01-03 22:15:40 · 题解

思路

考虑一下，若存在区间 [l,r]，区间和为 s，可以得出什么结论。(r-l+1\ge 2)

可以得出结论，若存在区间 [l,r]，区间和为 s，满足 r-l+1\ge 2，那么必有一段区间的和为 s-2。

因此，只要整个序列中有一段区间和 sum 满足 s\le sum 且 sum 与 s 的奇偶性相同，那么 s 就是合法的。

那么只需要知道整个序列的和 sum1 以及和 sum1 奇偶性不同，且最大的区间和 sum2。

令 pl,pr 表示整个区间第一次和最后一次出现 1 的位置，可用 set 维护。

显然有 sum2=\max(\displaystyle\sum_{i=pl+1}^r a_i,\displaystyle\sum_{i=1}^{pr-1}a_i)，可用树状数组维护。

代码

#include <bits/stdc++.h>
using namespace std;
int t, n, q, a[200005], c[200005], s1[200005], s2[200005];
set<int> pos;
set<int>::iterator pl, pr;
void add(int x, int k) {
    while (x <= n) {
        c[x] += k;
        x += (x & -x);
    }
}
int query(int x) {
    int ret = 0;

    while (x) {
        ret += c[x];
        x -= (x & -x);
    }

    return ret;
}
bool check(int x) {
    int sum1 = query(n), sum2;

    if (x <= sum1 && x % 2 == sum1 % 2)
        return 1;

    pl = pos.begin(), pr = pos.end();

    if (!pos.size())
        return 0;

    sum2 = query(n) - query((*pl));
    pr--, sum2 = max(sum2, query((*pr) - 1));
    return x <= sum2 && x % 2 == sum2 % 2;
}
int main() {
    cin >> t;

    while (t--) {
        for (int i = 0; i <= n + 1; i++)
            c[i] = 0;

        cin >> n >> q;
        pos.clear();

        for (int i = 1; i <= n; i++) {
            cin >> a[i], add(i, a[i]);
            s1[i] = s1[i - 1] + a[i];
            s2[i] = s2[i + 1] + a[i];

            if (a[i] == 1)
                pos.insert(i);
        }

        while (q--) {
            int op, x, k;
            cin >> op >> x;

            if (op == 1) {
                if (check(x))
                    puts("YES");
                else
                    puts("NO");
            } else {
                cin >> k;

                if (a[x] == 1)
                    pos.erase(x);

                add(x, -a[x]), a[x] = k, add(x, a[x]);

                if (a[x] == 1)
                    pos.insert(x);
            }
        }
    }

    return 0;
}