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

ZhongYuLin · 2026-11-09 09:43:16 · 题解

最大子段和？也许这五个字已经足够了。

对行建立线段树，每个叶子节点存储这一行的信息。方便起见，我们假设这个线段树是满二叉树（但是下文不会用根节点表示区间的左右端点）。

既然要维护连通块之和与实现连通块加，最常见的思路就是使用并查集。如果我们给每个节点管辖的区间（设为 [l,r]）中的每个点（即 \{(x,y)|l\leq x\leq r,1\leq y\leq m\}）都建立并查集，这当然十分好维护，但是问题在于每次合并都是 O((r-l+1)m) 的，使得线段树根本没优化。

你立刻注意到，将左右儿子节点合并时（设区间为 [l,d],[d+1,r]），只有中间相邻的第 d,d+1 两行可能发生合并。如果有两个连通块分别处于 [l,d-1],[d+2,r]，那么它们在父节点中肯定也还是独立的两个连通块。于是对于每个线段树节点 [l,r]，只需要维护它的第 l 行与第 r 行的并查集。

具体来说，假设我们通过暴力得到了 [l,r] 内的并查集，点 i 的代表元为 f_i。那么，我们将第 l 行和第 r 行的 f_i 提取出来（共 2m 个），经过离散化后存储下来。这就是前文所述“维护它的第 l 行与第 r 行的并查集”所要维护的信息。例如，有如下情况：

则对于第一行第四、五列，第四行第三、四列，它们的代表元都是 f_i。

明确了要维护什么，合并时，就用一个 4m 大小的临时并查集合并起来再离散化一下就行了。连通块大小与区间和则更简单了。至于单点改颜色，直接重构一行是一个简单的实现。

但是你发现仅仅维护上述信息不足以支持你通过这道题，你还很难去处理连通块和与连通块加。先考虑询问连通块和：

1. 如果这个连通块恰好位于一个线段树区间 [l,r] 内，并且它覆盖了第 l 行或是第 r 行的一部分，那么我们已经存储了这样的信息，直接输出即可。

2. 如果这个连通块恰好位于一个线段树区间 [l,r] 内，并且不覆盖第 l 行或是第 r 行的任何部分。我们别无他法，只能向下递归。但至少我们知道，要么连通块全在左儿子，要么连通块全在右儿子，要么连通块跨过了中间。最后情况可以重新合并子节点来获得必要的信息，复杂度为 O(m)，故复杂度正确。

在实现上，为了确定这个连通块究竟是何物，我们从叶子节点开始，不断找它的父亲节点，根据自己是左/右儿子，判断与右/左儿子合并之后会造成什么影响。例如，现在询问 (2,3) 所属连通块的和：

你现在找到了第二行位置的叶子节点，发现 (2,3) 与 (2,4) 相邻，于是，有：

接下来，找父节点。父节点的区间是 [1,2]，而 [2,2] 是它的右儿子，于是看能否与左儿子的连通块合并。用 O(m) 发现可以合并，于是：

继续找父节点。父节点是 [1,4]，[1,2] 是它的左儿子，于是看能否与右儿子的连通块合并。同样，发现可以合并。于是：

但是注意，将两个线段树区间合并以后，可能会导致原先不连通的连通块连通起来。如果你漏了上图中的浅黄色方块，就错了。不过严格地按照之前区间合并的方法，应该能自然避免这个问题。

于是你完成了统计。如果连通块处于区间 [l,r] 内部（即 [l+1,r-1]），显然不可能再有新的连通块加入，结束统计即可。

那么，连通块加怎么办？我们可以效仿上文的步骤，先寻找 (x,y) 连通块，再给每个连通块一个懒标记。怎么下传？直接把两个儿子 [l,d],[d+1,r]找出来，O(m) 地重新合并，求出每个连通块对应父节点中的何种连通块，从而可以判断要不要给左右儿子下传。

区间和就是顺手的事。

故，我们就在 O(nm\alpha(m)+qm\log(n)\alpha(m)) 的时间复杂度，大常数 O(nm) 空间复杂度解决了这个题目。良心出题人没有卡我 490\mathrm{MB} 的内存。笔者把下传标记所要的全部信息都存下来了，因此实现有差异，不过本质与上文相同。

我让 ChatGPT 6.1Sol 把我的代码按题解意思重构了，然后让 deepseek 写了点注释。这种实现就是空间常数小但是时间常数大。

::::info[Code]{close}

#include<bits/stdc++.h>

using namespace std;
using ui=unsigned int;
const int M=10;
const int N=150000;
const int S=1<<19;

// 快速读写。所有运算都在 unsigned int 下自然溢出，等价于模 2^32。
struct IO{
    char in[1<<16],out[1<<16];
    int pos=0,len=0,used=0;

    int get(){
        if(pos==len){
            len=fread(in,1,sizeof(in),stdin);
            pos=0;
            if(!len)return EOF;
        }
        return in[pos++];
    }

    ui read(){
        int c=get();
        while(c<=' '&&c!=EOF)c=get();
        ui x=0;
        for(;c>='0'&&c<='9';c=get())x=x*10+c-'0';
        return x;
    }

    void write(ui x){
        if(used+11>int(sizeof(out)))flush();
        char digits[10];
        int count=0;
        do digits[count++]=x%10+'0';while(x/=10);
        while(count)out[used++]=digits[--count];
        out[used++]='\n';
    }

    void flush(){
        fwrite(out,1,used,stdout);
        used=0;
    }
}io;

struct Node{
    // 线段树节点管理一个行区间 [L,R]。
    // 只需要保存第 L 行和第 R 行的连通块信息：
    // id[0..m-1]   : 第 L 行每列所属连通块的代表位置；
    // id[m..2m-1]  : 第 R 行每列所属连通块的代表位置。
    // 代表位置取该连通块在上下边界中第一次出现的位置，范围 [0,2m)。
    //
    // sz[k] / sum[k] / add[k] 只在 k 是代表位置时有意义。
    // pending 表示 add 中是否可能存在非零标记，用来避免每次扫描整个 add 数组。
    int id[M*2],sz[M*2];
    ui sum[M*2],add[M*2],val;
    bool pending;
}t[S];

int n,m,q,base=1,height;
int a[N][M],cut[S/2],cells[S];
ui val[N][M];

// 临时并查集，每次 join(p) 时重新覆盖，只在本次合并中有效。
// [0,2m) 为左儿子的块编号槽位；
// [2m,4m) 为右儿子的块编号槽位。
// 只有对应儿子 sz[k]>0 的槽位才表示实际存在的块。
int fa[M*4],sz[M*4],outer[M*4];
ui sum[M*4];

int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}

// 给节点 p 中编号为 k 的连通块整体加 z。
// 同时维护这个块自己的 sum，以及整个节点 p 的 val。
void fix(int p,int k,ui z){
    if(!z)return;
    t[p].pending=1;
    t[p].add[k]+=z;
    t[p].sum[k]+=z*t[p].sz[k];
    t[p].val+=z*t[p].sz[k];
}

// 用左右儿子的边界块，临时合并出父节点 p 的连通块关系。
//
// weights = false：只需要连通关系和 sz，不需要临时 sum。
//                  用于 push_down、solve 中判断块属于谁。
// weights = true ：需要临时 sum，用于 push_up 重建父节点的 sum。
//
// 注意：join 只构造临时并查集，不直接写入 t[p]。
template<bool weights=false>
void join(int p){
    // 把左右儿子各 2m 个边界块塞进临时并查集。
    for(int side=0;side<2;++side){
        const Node &s=t[p*2+side];
        int offset=side*m*2;
        for(int i=0;i<m*2;++i){
            fa[offset+i]=offset+i;
            sz[offset+i]=s.sz[i];
            if constexpr(weights)sum[offset+i]=s.sum[i];
            outer[offset+i]=-1;
        }
    }

    // cut[p] 是右儿子的第一行下标，左儿子最后一行是 cut[p]-1。
    // 只有中间相邻的这两行可能把左右儿子的连通块接起来。
    int mid=cut[p];
    if(mid<n)
        for(int i=0;i<m;++i)
            if(a[mid-1][i]==a[mid][i]){
                int x=find(t[p*2].id[m+i]);
                int y=find(m*2+t[p*2+1].id[i]);
                if(x==y)continue;
                if(sz[x]<sz[y])swap(x,y);
                fa[y]=x;
                sz[x]+=sz[y];
                if constexpr(weights)sum[x]+=sum[y];
            }

    // 父节点真正保存的是它自己的上边界（左儿子上边界）
    // 和下边界（右儿子下边界），共 2m 个位置。
    // 对每个临时连通块，记录它在父节点边界中第一次出现的位置。
    // outer[k] == -1 表示这个连通块完全藏在父节点内部，父节点不保存它。
    for(int i=0;i<m*2;++i){
        int k=i<m?t[p*2].id[i]:m*2+t[p*2+1].id[i];
        k=find(k);
        if(sz[k]&&outer[k]==-1)outer[k]=i;
    }
}

// 用左右儿子重建节点 p 的边界信息。
void push_up(int p){
    join<true>(p);
    t[p]={};

    // 只保存接触父节点外边界的连通块。
    // 同一个连通块可能在边界出现多次，这里用 outer[k] 作为父节点内的块编号。
    for(int i=0;i<m*2;++i){
        int k=i<m?t[p*2].id[i]:m*2+t[p*2+1].id[i];
        k=find(k);
        if(!sz[k])continue;
        int x=t[p].id[i]=outer[k];
        t[p].sz[x]=sz[k];
        t[p].sum[x]=sum[k];
    }

    // 整个区间的点权和就是左右儿子点权和相加。
    t[p].val=t[p*2].val+t[p*2+1].val;
}

// 把节点 p 的懒标记下传到左右儿子。
void push_down(int p){
    if(!t[p].pending)return;

    // 特判：如果父节点整段就是一个连通块，那么父节点的 add 只可能挂在
    // t[p].id[0] 上，并且应该下发给左右儿子中的所有非空块。
    if(t[p].sz[t[p].id[0]]==cells[p]){
        ui z=t[p].add[t[p].id[0]];
        for(int s=p*2;s<=p*2+1;++s)
            for(int k=0;k<m*2;++k)
                if(t[s].sz[k])fix(s,k,z);
        t[p].add[t[p].id[0]]=0;
        t[p].pending=0;
        return;
    }

    // 一般情况：先利用父子两层的 id 对应关系。
    // 儿子中接触父节点外边界的块（左儿子上边界、右儿子下边界）可以直接映射；
    // 只有完全藏在接缝处的儿子块，才需要模拟合并来找它属于父节点哪个块。
    int parent[M*4];
    fill(parent,parent+m*4,-1);
    for(int side=0;side<2;++side)
        for(int i=0;i<m;++i){
            int pos=side*m+i;
            parent[side*m*2+t[p*2+side].id[pos]]=t[p].id[pos];
        }

    bool joined=0;
    for(int side=0;side<2;++side)
        for(int k=0;k<m*2;++k){
            int s=p*2+side;
            if(!t[s].sz[k])continue;

            int x=parent[side*m*2+k];
            if(x==-1){
                // 这个儿子块不直接接触父节点外边界，需要 join 一次才能知道它属于谁。
                if(!joined)join(p),joined=1;
                x=outer[find(side*m*2+k)];
            }
            if(x!=-1)fix(s,k,t[p].add[x]);
        }

    fill(t[p].add,t[p].add+m*2,0u);
    t[p].pending=0;
}

// 把根到 p 路径上的懒标记一路下推，保证访问 p 时 p 的信息是最新的。
void descend(int p){
    for(int i=height;i;--i)push_down(p>>i);
}

// 重建第 x 行对应的叶子。
// 叶子只有一行，所以它的上边界和下边界都是这一行。
void init(int x){
    int p=base+x;
    t[p]={};
    for(int i=0;i<m;++i){
        // 同一行内，相邻同色格子属于同一个连通块。
        int k=i&&a[x][i]==a[x][i-1]?t[p].id[i-1]:i;
        t[p].id[i]=t[p].id[m+i]=k;
        ++t[p].sz[k];
        t[p].sum[k]+=val[x][i];
        t[p].val+=val[x][i];
    }
}

void build(){
    while(base<n)base<<=1,++height;

    for(int i=0;i<n;++i){
        init(i);
        cells[base+i]=m;
    }

    for(int p=base-1;p;--p){
        // cut[p] 是右儿子的第一行在原始数组中的下标。
        // 补齐出来的空行始终为空，不参与真正的合并。
        cut[p]=(p*2+1)*(base>>(__lg(p)+1))-base;
        cells[p]=cells[p*2]+cells[p*2+1];
        push_up(p);
    }
}

// 单点改颜色。
void update(int x,int y,int color){
    if(a[x][y]==color)return;

    int p=base+x;
    descend(p);

    // 重构叶子前，先把挂在叶子块上的 add 结算到每个格子的真实权值 val 中。
    for(int i=0;i<m;++i)
        val[x][i]+=t[p].add[t[p].id[i]];

    a[x][y]=color;
    init(x);

    // 自底向上重建祖先。
    while(p>>=1)push_up(p);
}

// 查询 (x,y) 所在连通块的点权和；
// 如果 z != 0，则同时给这个连通块整体加 z。
ui solve(int x,int y,ui z=0){
    int p=base+x;
    descend(p);

    // 先看叶子内部，得到该位置所属块。
    int k=t[p].id[y];
    ui ans=t[p].sum[k];

    // 从叶子往上爬，不断把当前连通块扩展到父节点。
    while(p>1){
        int child=p;
        p>>=1;

        // 父节点边界中，左儿子对应前 m 个位置，右儿子对应后 m 个位置。
        int pos=(child&1)*m;

        // 情况 1：目标块在 child 的“父节点外边界”那一侧出现过。
        // 那么可以直接通过 id 找到它在父节点中的块编号，不需要模拟合并。
        int i=0;
        while(i<m&&t[child].id[pos+i]!=k)++i;
        if(i<m){
            k=t[p].id[pos+i];
            ans=t[p].sum[k];
            continue;
        }

        // 情况 2：父节点整段已经是一个连通块。
        // 那么目标块必然就是这个唯一块，也无须模拟合并。
        if(t[p].sz[t[p].id[0]]==cells[p]){
            k=t[p].id[0];
            ans=t[p].sum[k];
            continue;
        }

        // 情况 3：需要临时合并左右儿子，判断目标块在父节点中属于谁。
        join(p);
        int root=find((child&1)*m*2+k);
        k=outer[root];

        // 目标块接触父节点外边界，父节点保存了它，可以继续往上走。
        if(k!=-1){
            ans=t[p].sum[k];
            continue;
        }

        // 目标块在父节点中已经完全封闭，只在临时并查集中存在，父节点不会保存它。
        // 此时这个连通块不可能再和父节点外部合并。
        ans=0;
        for(int side=0;side<2;++side)
            for(int j=0;j<m*2;++j){
                int s=p*2+side;
                if(t[s].sz[j]&&find(side*m*2+j)==root){
                    ans+=t[s].sum[j];
                    if(z)fix(s,j,z);
                }
            }

        if(z){
            ui delta=z*sz[root];
            // 封闭块不影响本节点及祖先的任何边界块，只改整段总和。
            for(int s=p;s;s>>=1)t[s].val+=delta;
        }
        break;
    }

    if(z){
        // 如果一路走到根都没有封闭，就把懒标记挂在根中对应的边界块上。
        if(k!=-1)fix(p,k,z);
    }
    return ans;
}

// 查询第 l 行到第 r 行的区间点权和。
ui query(int l,int r){
    l+=base;
    r+=base;

    // 先把 l、r 路径上的懒标记下推，公共祖先只下推一次。
    for(int i=height;i;--i){
        push_down(l>>i);
        if((l>>i)!=(r>>i))push_down(r>>i);
    }

    ui ans=0;
    for(;l<=r;l>>=1,r>>=1){
        if(l&1)ans+=t[l++].val;
        if(!(r&1))ans+=t[r--].val;
    }
    return ans;
}

int main(){
    n=io.read();
    m=io.read();
    q=io.read();

    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
            a[i][j]=io.read();

    build();

    while(q--){
        int op,x,y;
        op=io.read();
        x=io.read();
        y=io.read();
        --x;
        --y;

        if(op==1){
            int color;
            color=io.read();
            update(x,y,color);
        }

        if(op==2){
            ui z;
            z=io.read();
            solve(x,y,z);
        }

        if(op==3)io.write(solve(x,y));

        if(op==4)io.write(query(x,y));
    }

    io.flush();
    return 0;
}

::::