题解：P17858 「GLR-R5」处暑 / defervit

· · 题解

思路

按行建线段树。每个节点用小并查集维护连通块，记录块的大小、权值和及加法标记。

一个块只有接触区间的 l 或 r，才可能与外面连通，所以每个节点只需向父亲传递 O(m) 个块。合并两个儿子时，枚举中间相邻两行，颜色相同就合并对应的块。不再接触边界的块留在当前节点，这类块只有 O(m) 个。

忽略并查集的复杂度，总时间复杂度是 O((n+q)m\log n)。

代码

#include<bits/stdc++.h>
using namespace std;
#define ui uint32_t
#define uc unsigned char
const int N = 1.5e5 + 10, M = 41;
int n, m, q, c[N][11], id[N];
ui a[N][11];
struct node {
    int pa, sz[M];
    ui sum[M], tag[M], all;
    uc f[M], up[M], b[21];
    bool flag;
} tr[N << 1];
inline int find(int p, int x) {
    return tr[p].f[x] == x ? x : tr[p].f[x] = find(p, tr[p].f[x]);
}
inline void merge(int p, int x, int y) {
    x = find(p, x), y = find(p, y);
    if (x == y) return;
    if (tr[p].sz[x] < tr[p].sz[y]) swap(x, y);
    tr[p].f[y] = x;
    tr[p].sz[x] += tr[p].sz[y];
    tr[p].sum[x] += tr[p].sum[y];
}
inline void put(int p, int x, ui z) {
    ui v = z * (ui)tr[p].sz[x];
    tr[p].sum[x] += v;
    tr[p].tag[x] += z;
    tr[p].all += v;
    tr[p].flag = true;
}
inline void leaf(int p, int x) {
    node &t = tr[p];
    if (t.flag)
        for (int j = 1; j <= m; j ++)
            a[x][j] += t.tag[t.f[j]];
    t.flag = false, t.all = 0;
    for (int j = 1; j <= m; j ++) {
        t.f[j] = j, t.up[j] = 0, t.sz[j] = 1;
        t.sum[j] = a[x][j], t.tag[j] = 0;
        t.all += a[x][j];
    }
    for (int j = 2; j <= m; j ++)
        if (c[x][j] == c[x][j - 1]) merge(p, j, j - 1);
    for (int j = 1; j <= m; j ++)
        t.b[j] = t.b[j + m] = t.f[j] = find(p, j);
}
inline void copy(int p, int v, int d) {
    int pos[M] = {};
    for (int j = 1; j <= 2 * m; j ++) {
        int x = tr[v].b[j], k = d + j;
        if (pos[x]) tr[p].f[k] = pos[x];
        else {
            pos[x] = k;
            tr[p].sz[k] = tr[v].sz[x];
            tr[p].sum[k] = tr[v].sum[x];
        }
        tr[v].up[x] = k;
    }
}
inline void pushup(int p, int l, int r) {
    int mid = (l + r) >> 1;
    int ls = p + 1, rs = p + 2 * (mid - l + 1);
    node &t = tr[p];
    t.flag = false, t.all = tr[ls].all + tr[rs].all;
    for (int i = 1; i <= 4 * m; i ++) {
        t.f[i] = i, t.up[i] = 0;
        t.sz[i] = t.sum[i] = t.tag[i] = 0;
    }
    copy(p, ls, 0), copy(p, rs, 2 * m);
    for (int j = 1; j <= m; j ++)
        if (c[mid][j] == c[mid + 1][j])
            merge(p, m + j, 2 * m + j);
    for (int i = 1; i <= 4 * m; i ++) t.f[i] = find(p, i);
    for (int j = 1; j <= m; j ++) {
        t.b[j] = t.f[j];
        t.b[m + j] = t.f[3 * m + j];
    }
}
inline void down(int p, int v, int d) {
    for (int j = 1; j <= 2 * m; j ++) {
        int x = tr[v].b[j], k = d + j;
        if (tr[v].up[x] != k) continue;
        ui z = tr[p].tag[tr[p].f[k]];
        if (z) put(v, x, z);
    }
}
inline void pushdown(int p, int l, int r) {
    if (!tr[p].flag) return;
    int mid = (l + r) >> 1;
    down(p, p + 1, 0);
    down(p, p + 2 * (mid - l + 1), 2 * m);
    memset(tr[p].tag, 0, sizeof(tr[p].tag));
    tr[p].flag = false;
}
inline void build(int p, int l, int r, int fa) {
    tr[p].pa = fa;
    if (l == r) {
        id[l] = p;
        leaf(p, l);
        return;
    }
    int mid = (l + r) >> 1;
    build(p + 1, l, mid, p);
    build(p + 2 * (mid - l + 1), mid + 1, r, p);
    pushup(p, l, r);
}
inline void change(int p, int l, int r, int x, int y, int z) {
    if (l == r) {
        c[x][y] = z;
        leaf(p, l);
        return;
    }
    pushdown(p, l, r);
    int mid = (l + r) >> 1;
    if (x <= mid) change(p + 1, l, mid, x, y, z);
    else change(p + 2 * (mid - l + 1), mid + 1, r, x, y, z);
    pushup(p, l, r);
}
inline ui work(int x, int y, ui z, bool op) {
    int p = id[x], k = tr[p].f[y];
    while (tr[p].up[k]) {
        k = tr[p].up[k], p = tr[p].pa;
        k = tr[p].f[k];
    }
    if (!op) return tr[p].sum[k];
    ui v = z * (ui)tr[p].sz[k];
    put(p, k, z);
    for (p = tr[p].pa; p; p = tr[p].pa) tr[p].all += v;
    return 0;
}
inline ui ask(int p, int l, int r, int x, int y) {
    if (x <= l && r <= y) return tr[p].all;
    pushdown(p, l, r);
    int mid = (l + r) >> 1;
    ui res = 0;
    if (x <= mid) res += ask(p + 1, l, mid, x, y);
    if (y > mid)
        res += ask(p + 2 * (mid - l + 1), mid + 1, r, x, y);
    return res;
}
signed main() {
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++) cin >> c[i][j];
    build(1, 1, n, 0);
    while (q --) {
        int op, x, y, z;
        ui v;
        cin >> op >> x >> y;
        if (op == 1) {
            cin >> z;
            if (c[x][y] != z) change(1, 1, n, x, y, z);
        } else if (op == 2) {
            cin >> v;
            work(x, y, v, 1);
        } else if (op == 3) {
            cout << work(x, y, 0, 0) << '\n';
        } else {
            cout << ask(1, 1, n, x, y) << '\n';
        }
    }
    return 0;
}