题解：P12846 [蓝桥杯 2025 国 A] 翻转硬币

· · 题解

分析

看到区间反转问题，一般都是想到线段树加上懒修改功能。

但是这里要我们间隔修改，和隔两个修改。

对于间隔修改，把下标 i \mod2 \equiv j\mod2 相同的放一个线段树里，放两个线段树就是区间修改了。

对于隔两个修改，我们可以把下标 i \mod3 \equiv j\mod3 的放一个线段树里，放三个线段树就是区间修改了。

但信息不好同步，这里直接取最小公倍数就好了，放到 6 个线段树里。共同使用,然后每次修改和查询只需在对应树修改和查询对应区间即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
vector<int> f;
int Ls[6];
vector<vector<int>> a;
vector<vector<int>> t;
vector<vector<bool>> lz;

void bld(int c, int p, int l, int r) {
    if (l == r) {
        t[c][p] = a[c][l];
        return;
    }
    int mid = (l + r) >> 1;
    bld(c, p<<1, l, mid);
    bld(c, p<<1|1, mid+1, r);
    t[c][p] = t[c][p<<1] + t[c][p<<1|1];
}

void apply(int c, int p, int l, int r) {
    t[c][p] = (r - l + 1) - t[c][p];
    lz[c][p] = !lz[c][p];
}

void push(int c, int p, int l, int r) {
    if (!lz[c][p]) return;
    int mid = (l + r) >> 1;
    apply(c, p<<1, l, mid);
    apply(c, p<<1|1, mid+1, r);
    lz[c][p] = false;
}

void upd(int c, int p, int l, int r, int Lq, int Rq) {
    if (Lq > r || Rq < l) return;
    if (Lq <= l && r <= Rq) {
        apply(c, p, l, r);
        return;
    }
    push(c, p, l, r);
    int mid = (l + r) >> 1;
    upd(c, p<<1, l, mid, Lq, Rq);
    upd(c, p<<1|1, mid+1, r, Lq, Rq);
    t[c][p] = t[c][p<<1] + t[c][p<<1|1];
}

int qry(int c, int p, int l, int r, int Lq, int Rq) {
    if (Lq > r || Rq < l) return 0;
    if (Lq <= l && r <= Rq) {
        return t[c][p];
    }
    push(c, p, l, r);
    int mid = (l + r) >> 1;
    return qry(c, p<<1, l, mid, Lq, Rq) + qry(c, p<<1|1, mid+1, r, Lq, Rq);
}

void solve() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    f.resize(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> f[i];
    }
    for (int r = 0; r < 6; r++) {
        if (r == 0) {
            Ls[r] = n / 6;
        } else {
            if (n >= r) Ls[r] = (n - r) / 6 + 1;
            else Ls[r] = 0;
        }
    }
    a.assign(6, vector<int>());
    for (int r = 0; r < 6; r++) {
        if (Ls[r] > 0) a[r].assign(Ls[r], 0);
    }
    for (int i = 1; i <= n; i++) {
        int mod = i % 6;
        int idx;
        if (mod == 0) idx = i/6 - 1;
        else idx = (i - mod) / 6;
        a[mod][idx] = f[i];
    }
    t.assign(6, vector<int>());
    lz.assign(6, vector<bool>());
    for (int r = 0; r < 6; r++) {
        if (Ls[r] > 0) {
            t[r].assign(4 * Ls[r] + 5, 0);
            lz[r].assign(4 * Ls[r] + 5, false);
            bld(r, 1, 0, Ls[r] - 1);
        }
    }
    for (int qi = 0; qi < m; qi++) {
        int typ, x, y;
        cin >> typ >> x >> y;
        if (typ == 1) {
            int modx = x % 2;
            for (int r = 0; r < 6; r++) {
                if (r % 2 != modx) continue;
                int d = (r - x%6 + 6) % 6;
                int i0 = x + d;
                if (i0 > y) continue;
                int cnt = (y - i0) / 6;
                int i1 = i0 + cnt * 6;
                int j0, j1;
                if (r == 0) {
                    j0 = i0/6 - 1;
                    j1 = i1/6 - 1;
                } else {
                    j0 = (i0 - r)/6;
                    j1 = (i1 - r)/6;
                }
                if (j0 <= j1) upd(r, 1, 0, Ls[r]-1, j0, j1);
            }
        } else if (typ == 2) {
            int modx = x % 3;
            for (int r = 0; r < 6; r++) {
                if (r % 3 != modx) continue;
                int d = (r - x%6 + 6) % 6;
                int i0 = x + d;
                if (i0 > y) continue;
                int cnt = (y - i0) / 6;
                int i1 = i0 + cnt * 6;
                int j0, j1;
                if (r == 0) {
                    j0 = i0/6 - 1;
                    j1 = i1/6 - 1;
                } else {
                    j0 = (i0 - r)/6;
                    j1 = (i1 - r)/6;
                }
                if (j0 <= j1) upd(r, 1, 0, Ls[r]-1, j0, j1);
            }
        } else if (typ == 3) {
            for (int r = 0; r < 6; r++) {
                if (Ls[r] == 0) continue;
                int d = (r - x%6 + 6) % 6;
                int i0 = x + d;
                if (i0 > y) continue;
                int cnt = (y - i0) / 6;
                int i1 = i0 + cnt * 6;
                int j0, j1;
                if (r == 0) {
                    j0 = i0/6 - 1;
                    j1 = i1/6 - 1;
                } else {
                    j0 = (i0 - r)/6;
                    j1 = (i1 - r)/6;
                }
                if (j0 <= j1) upd(r, 1, 0, Ls[r]-1, j0, j1);
            }
        } else if (typ == 4) {
            int ans = 0;
            for (int r = 0; r < 6; r++) {
                if (Ls[r] == 0) continue;
                int d = (r - x%6 + 6) % 6;
                int i0 = x + d;
                if (i0 > y) continue;
                int cnt = (y - i0) / 6;
                int i1 = i0 + cnt * 6;
                int j0, j1;
                if (r == 0) {
                    j0 = i0/6 - 1;
                    j1 = i1/6 - 1;
                } else {
                    j0 = (i0 - r)/6;
                    j1 = (i1 - r)/6;
                }
                if (j0 <= j1) ans += qry(r, 1, 0, Ls[r]-1, j0, j1);
            }
            cout << ans << "\n";
        }
    }
    return ;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

时间复杂度

O(n\log n)