2022.02.27 CF811E Vladik and Entertaining Flags

https://www.luogu.com.cn/problem/CF811E

在一个 n*m 的网格上每个格子都有颜色，q 次询问，每次询问只保留 l 至 r 列时有多少个四连通的颜色块。两个格子同色但不连通算在不同的颜色块内。

这道题我首先大力找到一个错误规律，这个暂且不说，直接上正解。

对于每一列的格子搞线段树，记录每列有几个连通块，每列的最左侧和最右侧的节点属于哪个连通块。

合并的时候合并两个连通块相邻的两列，如果颜色一致并且fa不一样，总连通块的数量减一。不过需要初始化一下相邻两列格子的并查集。

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
int n,m,q,mapi[15][N],fa[N*15];
int tot;
struct node{
    int x,y,L[15],R[15],sum;
}t[N<<4];

inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*w;
}
inline int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
inline node update(node x,node y,int l,int r){
    node ans;
    ans.sum=x.sum+y.sum;
    for(int i=1;i<=n;i++)
    fa[x.L[i]]=x.L[i],fa[x.R[i]]=x.R[i],
    fa[y.L[i]]=y.L[i],fa[y.R[i]]=y.R[i];
    for(int i=1;i<=n;i++)ans.L[i]=x.L[i],ans.R[i]=y.R[i];
    for(int i=1;i<=n;i++)
    if(mapi[i][l]==mapi[i][r]){
        int xi=find(fa[x.R[i]]);
        int yi=find(fa[y.L[i]]);
        if(xi!=yi)fa[xi]=yi,--ans.sum;
    }
    for(int i=1;i<=n;i++)
    ans.L[i]=find(ans.L[i]),ans.R[i]=find(ans.R[i]);
    return ans;
}
inline void build(int x,int l,int r){
    if(l==r){
        for(int i=1;i<=n;i++)
        if(mapi[i][l]==mapi[i-1][l])
        t[x].L[i]=t[x].R[i]=t[x].L[i-1];
        else t[x].L[i]=t[x].R[i]=++tot,++t[x].sum;
        return ;
    }
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    t[x]=update(t[x<<1],t[x<<1|1],mid,mid+1);
}
inline node query(int x,int l,int r,int L,int R){
    if(l>=L&&r<=R)return t[x];
    int mid=(l+r)>>1;
    int flaga=0,flagb=0;
    node a,b,ans;
    if(L<=mid)a=query(x<<1,l,mid,L,R),flaga=1;
    if(R>mid)b=query(x<<1|1,mid+1,r,L,R),flagb=1;
    if(flaga&&!flagb)ans=a;
    else if(flagb&&!flaga)ans=b;
    else if(flaga&&flagb)ans=update(a,b,mid,mid+1);
    return ans;
}

signed main(){
    n=read();m=read();q=read();
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)mapi[i][j]=read();
    //cout<<"Case 1 "<<endl;
    build(1,1,m);
    //cout<<"Case 2 "<<endl;
    for(int i=1;i<=q;i++){
        int u,v;
        u=read();v=read();
        node fin=query(1,1,m,u,v);
        cout<<fin.sum<<endl;
    }
    return 0;
}