数列分块入门 8

LibreOJ-6284-数列分块入门 8

分析

• 查询区间内等于某个值$c$的元素个数
• 区间染色

实现

#include <iostream>
#include <cmath>
using namespace std;

const int N = 100010, T = 320;
int n, a[N];
int pos[N], L[T], R[T];
bool mark[T];
int color[T];

void initialize () {
    int t = sqrt(n);
    for (int i = 1; i <= t; ++ i) {
        L[i] = R[i - 1] + 1;
        R[i] = i * t;
    }
    if (R[t] < n) {
        ++ t;
        L[t] = R[t - 1] + 1;
        R[t] = n;
    }

    for (int i = 1; i <= t; ++ i)
        for (int j = L[i]; j <= R[i]; ++ j)
            pos[j] = i;
}
void update (int k) {
    if (mark[k] == false) return;

    mark[k] = false;
    for (int i = L[k]; i <= R[k]; ++ i)
        a[i] = color[k];
}
void modify (int l, int r, int val) { // a[l ~ r] = val
    int x = pos[l], y = pos[r];
    if (x == y) {
        update(x);
        for (int i = l; i <= r; ++ i) a[i] = val;
    } else {
        for (int i = x + 1; i <= y - 1; ++ i) {
            mark[i] = true;
            color[i] = val;
        }
        update(x);
        for (int i = l; i <= R[x]; ++ i) a[i] = val;
        update(y);
        for (int i = L[y]; i <= r; ++ i) a[i] = val;
    }
}
int query (int l, int r, int val) {
    int x = pos[l], y = pos[r];
    int res = 0;
    if (x == y) {
        update(x);
        for (int i = l; i <= r; ++ i)
            if (a[i] == val)
                ++ res;
    } else {
        for (int i = x + 1; i <= y - 1; ++ i) {
            if (mark[i] == true) {
                res += (color[i] == val ? R[i] - L[i] + 1 : 0);
            } else {
                for (int j = L[i]; j <= R[i]; ++ j)
                    if (a[j] == val)
                        ++ res;
            }
        }
        update(x);
        for (int i = l; i <= R[x]; ++ i)
            if (a[i] == val)
                ++ res;
        update(y);
        for (int i = L[y]; i <= r; ++ i)
            if (a[i] == val)
                ++ res;
    }
    return res;
}

int main () {
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> a[i];

    initialize();
    for (int i = 1, l, r, c; i <= n; ++ i) {
        cin >> l >> r >> c;
        cout << query(l, r, c) << endl;
        modify(l, r, c);
    }
    return 0;
}