分块入门 8

XXh0919 · 2025-09-12 18:40:45 · 题解

好久没写题解了，那就再写一篇。

解法

注意到区间推平操作，可以用珂朵莉树。但是我不会，所以考虑分块。先对序列分块，然后处理操作时，对于散块，我们直接暴力修改并统计答案；对于整块，直接暴力会导致时间复杂度到达 O(n)，所以我们可以“懒修改”，对整块打上修改的标记，等到需要处理这个整块的时候再把标记下放，就能将复杂度控制下来了。

还有，对于一个已经推平的块，操作时如果整个块都是目标值，我们就无须打标记，直接将块长累计到答案里，这样也能优化复杂度。

总时间复杂度 O(n\sqrt n)。

其实不想给代码的，但是因为感觉题解太短不好看，所以一不小心就把代码放上来了。

Code

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pi pair<int,int>
#define mkp(a,b) make_pair((a),(b)) 
#define IOS cin.tie(0)->sync_with_stdio(0)
using namespace std;
const int N = 1e6 + 15, mod = 10007;

int I_LOVE_CCF = 1;

int n, t;
int a[N], b[N];
int l[N], r[N], pos[N], add[N];

void init () {
    rep (i, 1, t) {
        l[i] = r[i - 1] + 1;
        r[i] = i * t;
    }
    r[t] = n;
    rep (i, 1, t) {
        rep (j, l[i], r[i]) {
            pos[j] = i;
        }
    }
}

void reset (int p) {
    if (add[p] == -1) return ;
    rep (i, l[p], r[p]) a[i] = add[p];
    add[p] = -1;
}

int update (int ll, int rr, int c) {
    int p = pos[ll], q = pos[rr];
    int ans = 0;
    if (p == q) {
        reset (p);
        rep (i, ll, rr) {
            if (a[i] == c) ++ ans;
            else a[i] = c;
        }
        return ans;
    }
    reset (p), reset (q);
    rep (i, ll, r[p]) {
        if (a[i] == c) ++ ans;
        else a[i] = c;
    }
    rep (i, l[q], rr) {
        if (a[i] == c) ++ ans;
        else a[i] = c;
    }//暴力！
    rep (i, p + 1, q - 1) {
        if (add[i] != -1) {
            if (add[i] != c) add[i] = c;//打标记
            else ans += r[i] - l[i] + 1;//如上文所言
        } else {
            rep (j, l[i], r[i]) {
                if (a[j] == c) ++ ans;
                else a[j] = c;
            }
            add[i] = c;
        }
    }
    return ans;
}

signed main () {
    IOS;
    memset (add, -1, sizeof add);
    cin >> n;
    t = sqrt (n);
    rep (i, 1, n) cin >> a[i];
    init ();
    rep (i, 1, n) {
        int l, r, c;
        cin >> l >> r >> c;
        cout << update (l, r, c) << endl;
    }
    return --I_LOVE_CCF;
}