题解：P13983 数列分块入门 8

xAlec · 2025-09-06 17:03:46 · 题解

Solution

区间询问等于一个数 c 的元素，然后区间覆盖为 c。

用珂朵莉树做这题会很好做，本人不会。

其实分块也还好做，考虑给每个块打覆盖标记，修改整块的时候更新当前块的标记，修改散块的时候需要下放标记将其所在块都修改成标记，若当前散块没有标记是不用更新标记的，直接暴力修改 a_i \leftarrow c。

查询的话边修改边统计就行，依旧是块长取 \sqrt{n} 时复杂度最小为 O(n\sqrt{n})。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int res = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) f = ch == '-' ? -1 : 1, ch = getchar();
    while (isdigit(ch)) res = (res << 1) + (res << 3) + (ch ^ 48), ch = getchar();
    return res * f;
}
constexpr int MAXN = 3e5 + 10;
int n, A[MAXN], tag[MAXN], blk[MAXN], maxblk, siz;

inline void Update (int pos) {
    if (!~tag[pos]) return;
    int l = (pos - 1) * siz + 1, r = min (pos * siz, n);
    for (int i = l; i <= r; i ++) A[i] = tag[pos];
    tag[pos] = -1;
}
inline int ModifyA (int ql, int qr, int c) {
    int tmpSum = 0, pos = blk[ql];
    if (tag[pos] == c) {
        tmpSum += (qr - ql + 1);
    } else if (!~tag[pos]) {
        // tag[pos] = c;
        for (int i = ql; i <= qr; i ++) {
            tmpSum += (A[i] == c);
            if (A[i] ^ c) A[i] = c;
        }
    } else {
        Update (pos);
        for (int i = ql; i <= qr; i ++) A[i] = c;
    }
    return tmpSum;
}
inline int ModifyB (int pos, int c) {
    int tmpSum = 0, l = (pos - 1) * siz + 1, r = min (pos * siz, n);
    if (tag[pos] == c) {
        tmpSum += siz;
    } else if (!~tag[pos]) {
        tag[pos] = c;
        for (int i = l; i <= r; i ++) {
            tmpSum += (A[i] == c);
            if (A[i] ^ c) A[i] = c;
        }
    } else {
        tag[pos] = c;
    }
    return tmpSum;
}
inline int Query (int ql, int qr, int c) {
    int lpos = blk[ql], rpos = blk[qr], Answer = 0;
    if (lpos == rpos) {
        Answer += ModifyA (ql, qr, c);
    } else {
        Answer += ModifyA (ql, min (lpos * siz, n), c);
        Answer += ModifyA ((rpos - 1) * siz + 1, qr, c);
        for (int i = lpos + 1; i <= rpos - 1; i ++) Answer += ModifyB (i, c);
    }
    return Answer;
}

signed main() {
    n = read(), siz = sqrt(n);
    memset (tag, -1, sizeof (tag));
    for (int i = 1; i <= n; i ++) {
        A[i] = read();
        blk[i] = (i - 1) / siz + 1;
    }
    maxblk = blk[n];
    int l = 0, r = 0, c = 0;
    for (int i = 1; i <= n; i ++) {
        l = read(), r = read(), c = read();
        printf ("%lld\n", Query (l, r, c));
    }
    return 0;
}