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

· · 题解

闲话

这里是地狱吗。

我是T2首A，可惜不是最短。

正文

首先 m \leq 10，想到以行为下标建线段树，维护连通块，非常难搞啊，首先要发现对于每个区间只会向父亲传递其过边界连通块的信息，又过边界连通块数量是 \mathcal{O(m)} 的，所以对于每个区间我们维护以下东西：

好你现在就会做了要考虑怎么 pushup 了。

首先把右子树的过边界连通块的编号整体加左子树过边界连通块数量，再开个临时并查集，方便合并，枚举 1 \leq i \leq m 对于 c_{mid, i} = c_{mid + 1, i} 合并 bt_{ls}, cnt1_{ls} + tp_{rs}，然后对能到达左右边界的重编号并计算 cnt1，再对左右子树的过边界连通块但没过当前节点边界的连通块继续重编号，计算 cnt2，在做这些操作时顺带记录一个 rt 表示并查集代表元为 i 的连通块重编号后的编号，这样 btid, siz, sum 等信息就可以愉快的合并了。pushdown 比较简单，就不讲了。

然后改颜色直接暴力重构那一行再 pushup 即可。

极大连通块加 z 则是定位到在线段树上该连通块第一次不作为过边界连通块的结点编号 id，设该连通块在 id 里的存储编号为 i（cnt1_{id} < i \leq cnt2_{id}），add_i \leftarrow add_i + z, sum_i \leftarrow z \times siz_i。

查询连通块和同样是定位到 id 直接查询 sum_i 就好，区间查询简单。

运气比较好，改了几个手滑的错误就过了。

/*
address:https://www.luogu.com.cn/problem/P17858
AC 2026/11/8 9:59
*/
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
const int N = 1.5e5 + 5;
ui n, m, q;
int col[N][12], row[N][12];
ui val[N][12];
inline int find(int* fa, int x) { return fa[x] == x ? x : fa[x] = find(fa, fa[x]); }
inline void merge(int* fa, int x, int y) { fa[find(fa, x)] = find(fa, y); }
struct SegmentTree {
#define ls (id << 1)
#define rs (id << 1 | 1)
#define mid (l + r >> 1)
    struct Segment {
        ui all;
        ui cnt1, cnt2;
        ui bt[12], tp[12];
        ui btid[25], tpid[25];
        ui siz[50], sum[50], add[50];
    }seg[N << 2];
    inline void pushup(int id, int l, int r) {
        int fa[50];
        int n = seg[ls].cnt1 + seg[rs].cnt1;
        for (int i = 1;i <= n;++i) fa[i] = i;
        for (int i = 1;i <= m;++i)
            if (col[mid][i] == col[mid + 1][i]) merge(fa, seg[ls].bt[i], seg[ls].cnt1 + seg[rs].tp[i]);
        int tchtp = 0, tchbt = 0;
        for (int i = 1;i <= m;++i)
            tchtp |= 1 << find(fa, seg[ls].tp[i]),
            tchbt |= 1 << find(fa, seg[ls].cnt1 + seg[rs].bt[i]);
        int rt[50];
        for (int i = 1;i <= n;++i) rt[i] = -1;
        int j = 0, k = 0;
        for (int i = 1;i <= n;++i)
            if (find(fa, i) == i && (tchtp >> i & 1 || tchbt >> i & 1)) rt[i] = ++j;
        k = j;
        for (int i = 1;i <= n;++i)
            if (find(fa, i) == i && rt[i] == -1) rt[i] = ++k;
        seg[id].cnt1 = j, seg[id].cnt2 = k;
        for (int i = 1;i <= k;++i) seg[id].sum[i] = seg[id].siz[i] = 0;
        for (int i = 1;i <= seg[ls].cnt1;++i) {
            int p = rt[find(fa, i)];
            seg[id].tpid[i] = p;
            seg[id].siz[p] += seg[ls].siz[i];
            seg[id].sum[p] += seg[ls].sum[i];
        }
        for (int i = 1;i <= seg[rs].cnt1;++i) {
            int p = rt[find(fa, seg[ls].cnt1 + i)];
            seg[id].btid[i] = p;
            seg[id].siz[p] += seg[rs].siz[i];
            seg[id].sum[p] += seg[rs].sum[i];
        }
        for (int i = 1;i <= m;++i)
            seg[id].tp[i] = seg[id].tpid[seg[ls].tp[i]],
            seg[id].bt[i] = seg[id].btid[seg[rs].bt[i]];
        seg[id].all = seg[ls].all + seg[rs].all;
    }
    inline void update(int id, int i) {
        seg[id].cnt1 = seg[id].cnt2 = seg[id].all = 0;
        for (int j = 1;j <= m;++j) {
            int p;
            if (j == 1 || col[i][j] != col[i][j - 1]) p = ++seg[id].cnt2, seg[id].siz[p] = seg[id].sum[p] = 0;
            else p = row[i][j - 1];
            row[i][j] = p;
            ++seg[id].siz[p];
            seg[id].sum[p] += val[i][j];
            seg[id].all += val[i][j];
            seg[id].tp[j] = seg[id].bt[j] = p;
        }
        seg[id].cnt1 = seg[id].cnt2;
    }
    inline void pushdown(int id, int l, int r) {
        for (int i = 1;i <= seg[ls].cnt1;++i) {
            ui k = seg[id].add[seg[id].tpid[i]];
            if (k)
                seg[ls].sum[i] += k * seg[ls].siz[i],
                seg[ls].add[i] += k,
                seg[ls].all += k * seg[ls].siz[i];
        }
        for (int i = 1;i <= seg[rs].cnt1;++i) {
            ui k = seg[id].add[seg[id].btid[i]];
            if (k)
                seg[rs].sum[i] += k * seg[rs].siz[i],
                seg[rs].add[i] += k,
                seg[rs].all += k * seg[rs].siz[i];
        }
        for (int i = 1;i <= seg[id].cnt2;++i) seg[id].add[i] = 0;
    }
    inline void build(int id, int l, int r) {
        if (l == r) return update(id, l);
        build(ls, l, mid), build(rs, mid + 1, r);
        pushup(id, l, r);
    }
    inline void change(int id, int l, int r, int x, int y, int c) {
        if (l == r) {
            for (int i = 1;i <= m;++i) val[x][i] += seg[id].add[row[x][i]];
            for (int i = 1;i <= seg[id].cnt2;++i) seg[id].add[i] = 0;
            col[x][y] = c;
            update(id, x);
            return;
        }
        pushdown(id, l, r);
        if (x <= mid) change(ls, l, mid, x, y, c);
        else change(rs, mid + 1, r, x, y, c);
        pushup(id, l, r);
    }
    inline ui query(int id, int l, int r, int L, int R) {
        if (l >= L && R >= r) return seg[id].all;
        pushdown(id, l, r);
        ui ret = 0;
        if (L <= mid) ret += query(ls, l, mid, L, R);
        if (R > mid) ret += query(rs, mid + 1, r, L, R);
        return ret;
    }
}SGT;
struct CC {
    int id, rnk;
    int path[20], dep;
};
int path[20], d[20];
inline CC locate(int x, int y) {
    int dep = 0;
    int id = 1, l = 1, r = n;
    while (l < r) {
        path[++dep] = id;
        if (x <= mid) d[dep] = 0, id = ls, r = mid;
        else d[dep] = 1, id = rs, l = mid + 1;
    }
    int rnk = row[x][y];
    for (int i = dep;i > 0;--i) {
        int id = path[i];
        if (d[i]) rnk = SGT.seg[id].btid[rnk];
        else rnk = SGT.seg[id].tpid[rnk];
        if (rnk > SGT.seg[id].cnt1) {
            CC ret;ret.id = id, ret.dep = i, ret.rnk = rnk;
            for (int j = 1;j < i;++j) ret.path[j] = path[j];
            return ret;
        }
    }
    CC ret;ret.id = 1, ret.dep = 1, ret.rnk = rnk;
    return ret;
}
int main() {
    scanf("%u%u%u", &n, &m, &q);
    for (int i = 1;i <= n;++i)
        for (int j = 1;j <= m;++j) scanf("%d", &col[i][j]);
    SGT.build(1, 1, n);
    while (q--) {
        ui op;scanf("%d", &op);
        if (op == 1) {
            ui x, y, c;scanf("%u%u%u", &x, &y, &c);
            SGT.change(1, 1, n, x, y, c);
        }
        if (op == 2) {
            ui x, y, k;scanf("%u%u%u", &x, &y, &k);
            CC bel = locate(x, y);
            ui delta = k * SGT.seg[bel.id].siz[bel.rnk];
            SGT.seg[bel.id].sum[bel.rnk] += delta;
            SGT.seg[bel.id].add[bel.rnk] += k;
            SGT.seg[bel.id].all += delta;
            for (int j = 1;j < bel.dep;++j) SGT.seg[bel.path[j]].all += delta;
        }
        if (op == 3) {
            ui x, y;scanf("%u%u", &x, &y);
            CC bel = locate(x, y);
            printf("%u\n", SGT.seg[bel.id].sum[bel.rnk]);
        }
        if (op == 4) {
            ui l, r;scanf("%u%u", &l, &r);
            printf("%u\n", SGT.query(1, 1, n, l, r));
        }
    }
    return 0;
}