题解：P10308 「Cfz Round 2」Osmanthus

· · 题解

分析

当 a_i\ne0 时，循环节的长度 t 与 2 的整数次幂有关。这个规律在理性上官方题解已经证明，在感性上可以用打表的方法。

那么当 a_i=0 时，显然，如果 0 只出现在 a 数组的中间或结尾，那么对答案没有影响；如果 0 出现在了 a 数组的开头，那么这个 0 对于 a 数组来说是无关紧要的，因为任何数异或 0 都的它本身。

所以，我们可以在每次询问时，求出 a 数组的前缀 0 的个数。那么如何求呢，很容易得出一个暴力的方法。

int zero = 0;//代表0的个数
while (a[zero + 1] == 0 && zero + 1 <= n)
    zero++;

用这样的方法求明显是超时的，那么可以进行优化。

由于每次修改只修改了一个数，但每次都要重新计算一遍 0 的个数，所以浪费了很多时间。不妨用一个变量 la 记录修改前 a 数组的前缀 0 的数量，再看看修改操作会对 la 产生什么影响。

显然，当每次修改的 a_{x_i} 与 p_i 同为 0 或同不为 0 时，对 la 不会产生影响；反之，分为两种情况。

一：a_{x_i}=0,p_i\ne0，若 x_i 不在 la 的范围内，则不会有影响；否则，前缀 0 会在 x_i 这个位置断开，此时 zero=x_i-1。

二：a_{x_i}\ne0,p_i=0，若 x_i 远远超过了 la 的范围，那么也不会有影响。因为想要让 la 增加，只能在 la+1 这个位置接上一个 0，所以当 x_i=la+1 时，zero 应从 la+1 开始计算，用暴力的方法往后不断枚举，直到它对应的位置不为 0。

Code

#include <bits/stdc++.h>
using namespace std;
int a[300005], b[300005];

int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int la = 0;
    while (a[la + 1] == 0 && la + 1 <= n)
        la++;
    while (q--) {
        int x, p;
        cin >> x >> p;
        int zero = la;
        if (a[x] != 0 && p == 0) {
            if (x == la + 1) {
                zero = la + 1;
                while (a[zero + 1] == 0 && zero + 1 <= n)
                    zero++;
            }
        } else if (a[x] == 0 && p != 0) {
            if (x <= la)
                zero = x - 1;
        }
        la = zero;
        a[x] = p;
        if (n <= zero)
            cout << 1;
        else {
            int kk = n;
            kk -= zero;
            int ans = 0;
            for (int j = 1;; j *= 2) {
                if (j == 1)
                    ans++;
                else
                    ans += j / 2;
                if (kk <= ans) {
                    cout << j;
                    break;
                }
            }
        }
        cout << endl;
    }
}

赛时记录。

上述方法归根结底还是暴力的方法，这种方法可以通过可能是因为数据过水。

不过也可以用树状数组维护前缀和，而前缀 0 的个数即为最后一个前缀和为 0 的位置的下标，这个可以用二分实现。

附上代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[300005], b[300005];
int c[300005];
int n;

void add(int x, int y) {
    for (; x <= n; x += x & (-x))
        c[x] += y;
}

int ask(int x) {
    int ans = 0;
    for (; x; x -= x & (-x))
        ans += c[x];
    return ans;
}

signed main() {
    int q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        add(i, a[i]);
    }
    while (q--) {
        int x, p;
        cin >> x >> p;
        add(x, p - a[x]);
        a[x] = p;
        int l = 1, r = n, zero = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (ask(mid) == 0) {
                l = mid + 1;
                zero = mid;
            } else
                r = mid - 1;
        }
        if (n <= zero)
            cout << 1;
        else {
            int kk = n;
            kk -= zero;
            int ans = 0;
            for (int j = 1;; j *= 2) {
                if (j == 1)
                    ans++;
                else
                    ans += j / 2;
                if (kk <= ans) {
                    cout << j;
                    break;
                }
            }
        }
        cout << endl;
    }
}