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

chenbs · 2026-11-11 15:42:23 · 题解

你们的签到题怎么这么难写，这不评黑？

考虑对行建立线段树，对于每个节点，用一个并查集维护上下 2m 个边界点的连通性，以及与这些边界点相邻的连通块的信息。pushup 时，先把左右儿子放在一起，建立一个临时的 4m 个点的并查集，合并中间的相同的点之后，再把边上 2m 个点拿出来。

对于操作 1，就是正常的线段树单点修改，注意叶子处需要另外写一套 pushdown 和 pushup，用于把标记下传到真实的 a 数组中。

对于操作 2，考虑从下往上找到第一个不包含 x 的节点 u，在 u 的左右儿子打标记。这里可能涉及到多个连通块，因为一个连通块可以在左右儿子之间来回穿梭。

对于操作 3，和操作 2 相似。

对于操作 4 是平凡的，每个节点再记录一个总和即可。

注意操作 2,3 寻找节点之前，必须先把所有祖先的 tag 都下放。

我写的代码常数很大，可能要重复提交几次才能波动过去。

#include<bits/stdc++.h>
using namespace std;
int n,m,q,c[150005][11],pos[150005];
unsigned a[150005][11];
struct node {
    int fa[21],sz[21],l,r;
    unsigned tag[21],s[21],s2;
    int etag;
    int find(int x) {
        return fa[x]==x?x:fa[x]=find(fa[x]);
    }
    void merge(int x, int y) {
        x=find(x), y=find(y);
        if(x!=y) fa[x]=y, sz[y]+=sz[x], s[y]+=s[x];
    }
    void push(int x, unsigned y) {
        tag[x]+=y, s[x]+=sz[x]*y, s2+=sz[x]*y, etag=1;
    }
} t[600005];
struct DSU { // 临时使用一个 4m 个点的 dsu
    int fa[41],sz[41];
    unsigned s[41];
    int find(int x) {
        return fa[x]==x?x:fa[x]=find(fa[x]);
    }
    void merge(int x, int y) {
        x=find(x), y=find(y);
        if(x!=y) fa[x]=y, sz[y]+=sz[x], s[y]+=s[x];
    }
    void build(int u) {
        for(int i=1; i<=2*m; i++) {
            fa[i]=t[u<<1].fa[i], sz[i]=t[u<<1].sz[i], s[i]=t[u<<1].s[i];
            fa[i+2*m]=t[u<<1|1].fa[i]+2*m, sz[i+2*m]=t[u<<1|1].sz[i], s[i+2*m]=t[u<<1|1].s[i];
        }
        int mid=t[u].l+t[u].r>>1;
        for(int i=1; i<=m; i++)
            if(c[mid][i]==c[mid+1][i])
                merge(m+i,2*m+i);
    }
} dsu;
int nwrt[41];
void pushup(int u, int l, int r) {
    dsu.build(u);
    memset(nwrt,-1,sizeof nwrt);
    for(int i=1; i<=m; i++) nwrt[dsu.find(i)]=i, nwrt[dsu.find(3*m+i)]=m+i;
    for(int i=1; i<=4*m; i++) {
        if(dsu.find(i)==i && nwrt[i]!=-1) {
            int j=nwrt[i];
            t[u].sz[j]=dsu.sz[i], t[u].s[j]=dsu.s[i];
        }
    }
    for(int i=1; i<=m; i++) t[u].fa[i]=nwrt[dsu.find(i)], t[u].fa[i+m]=nwrt[dsu.find(3*m+i)];
    t[u].s2=t[u<<1].s2+t[u<<1|1].s2;
}
void pushdown(int u, int l, int r) {
    if(l==r || !t[u].etag) return;
    dsu.build(u);
    memset(nwrt,-1,sizeof nwrt);
    for(int i=1; i<=m; i++) nwrt[dsu.find(i)]=i, nwrt[dsu.find(3*m+i)]=m+i;
    for(int i=1; i<=2*m; i++) {
        if(t[u<<1].find(i)==i) {
            int x=nwrt[dsu.find(i)];
            if(x!=-1) t[u<<1].push(i,t[u].tag[x]);
        }
        if(t[u<<1|1].find(i)==i) {
            int x=nwrt[dsu.find(i+2*m)];
            if(x!=-1) t[u<<1|1].push(i,t[u].tag[x]);
        }
    }
    for(int i=1; i<=2*m; i++) t[u].tag[i]=0;
    t[u].etag=0;
}
void pdleaf(int u, int l) {
    for(int i=1; i<=m; i++) a[l][i]+=t[u].tag[t[u].find(i)];
    memset(t[u].tag,0,sizeof(t[u].tag));
}
void leaf(int u, int l) {
    for(int i=1; i<=m; i++) {
        t[u].fa[i]=t[u].fa[i+m]=i, t[u].sz[i]=1;
        t[u].s[i]=a[l][i];
    }
    for(int i=1; i<m; i++)
        if(c[l][i]==c[l][i+1])
            t[u].merge(i,i+1);
}
void build(int u, int l, int r) {
    t[u].l=l, t[u].r=r;
    if(l==r) {
        leaf(u,l), pos[l]=u;
        return;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid), build(u<<1|1,mid+1,r);
    pushup(u,l,r);
}
void update(int u, int l, int r, int x, int y, int z) {
    if(l==r) {
        pdleaf(u,l), c[x][y]=z, leaf(u,l);
        return;
    }
    pushdown(u,l,r);
    int mid=l+r>>1;
    if(x<=mid) update(u<<1,l,mid,x,y,z);
    else update(u<<1|1,mid+1,r,x,y,z);
    pushup(u,l,r);
}
void find(int x, int y, vector<pair<int,int> > &ve) {
    int u=pos[x];
    for(int j=__lg(u); j>=1; j--) pushdown(u>>j,t[u>>j].l,t[u>>j].r);
    int p=t[u].find(y);
    while(u>1) {
        dsu.build(u>>1);
        memset(nwrt,-1,sizeof nwrt);
        for(int i=1; i<=m; i++) nwrt[dsu.find(i)]=i, nwrt[dsu.find(3*m+i)]=m+i;
        if(u&1) {
            int p2=dsu.find(p+2*m);
            if(nwrt[p2]==-1) {
                for(int j=1; j<=2*m; j++)
                    if(t[u^1].find(j)==j && dsu.find(j)==p2)
                        ve.emplace_back(u^1,j);
                for(int j=1; j<=2*m; j++)
                    if(t[u].find(j)==j && dsu.find(j+2*m)==p2)
                        ve.emplace_back(u,j);
                return;
            } else {
                p=nwrt[p2], u>>=1;
            }
        } else {
            int p2=dsu.find(p);
            if(nwrt[p2]==-1) {
                for(int j=1; j<=2*m; j++)
                    if(t[u].find(j)==j && dsu.find(j)==p2)
                        ve.emplace_back(u,j);
                for(int j=1; j<=2*m; j++)
                    if(t[u^1].find(j)==j && dsu.find(j+2*m)==p2)
                        ve.emplace_back(u^1,j);
                return;
            } else {
                p=nwrt[p2], u>>=1;
            }
        }
    }
    ve.emplace_back(1,p);
}
unsigned query(int u, int l, int r, int x, int y) {
    if(x<=l && r<=y) return t[u].s2;
    pushdown(u,l,r);
    int mid=l+r>>1;
    unsigned res=0;
    if(x<=mid) res+=query(u<<1,l,mid,x,y);
    if(y>mid) res+=query(u<<1|1,mid+1,r,x,y);
    return res;
}

char buf[1<<20],*p1,*p2;
#define fast_getchar() (((p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))),*p1++)
int rd() {
    int s=0;
    char c=fast_getchar();
    while(c<48) c=fast_getchar();
    while(c>47) s=s*10+(c^48), c=fast_getchar();
    return s;
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    n=rd(), m=rd(), q=rd();
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            c[i][j]=rd();
    build(1,1,n);
    for(int i=1; i<=q; i++) {
        int op,x,y,z;
        op=rd(), x=rd(), y=rd();
        if(op==1) {
            z=rd();
            update(1,1,n,x,y,z);
        } else if(op==2) {
            z=rd();
            vector<pair<int,int>> ve;
            find(x,y,ve);
            for(auto [j,k]:ve) t[j].push(k,z);
            for(int j=ve[0].first>>1; j>=1; j>>=1) pushup(j,t[j].l,t[j].r);
        } else if(op==3) {
            unsigned ans=0;
            vector<pair<int,int>> ve;
            find(x,y,ve);
            for(auto [j,k]:ve) ans+=t[j].s[k];
            cout<<ans<<'\n';
        } else {
            cout<<query(1,1,n,x,y)<<'\n';
        }
    }
    return 0;
}