CF811E Vladik and Entertaining Flags

最近都是各种校内模拟赛，好久没写题解了。

题意

题解

用线段树维护列，每个线段树记录这个区间内：

1. 最左边一列每个方块所属的集合
2. 最右边所属的集合
3. 四联通颜色块个数，即答案

合并时对中间两列遍历所有行，如果两块颜色相同就用并查集把两个集合给合并起来，并将答案 $-1$ 。

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define mp make_pair
#define ha 1000000007
#define ui unsigned int
#define pii pair<int,int>
 
using namespace std;
 
inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int M=100005;
struct Tree {
    int l[15],r[15],res;
    Tree (int n=0) { res=n; }
} tree[M<<2];
int cnt,n,m,q,a,b,s[15][M],fa[15*M];

inline void init(int x) { fa[x]=x; }

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

inline bool merge(int x,int y)
{
    int gfx=getfa(x),gfy=getfa(y);
    if (gfx==gfy) return 0;
    return fa[gfx]=gfy,1;
}

#define ls x<<1
#define rs x<<1|1

inline Tree pushup(Tree x,Tree y,int mid) //合并
{
    Tree ans(x.res+y.res);
    for (int i=1;i<=n;i++) //初始化并查集
    {
        init(x.l[i]); init(x.r[i]);
        init(y.l[i]); init(y.r[i]);
    }
    for (int i=1;i<=n;i++)
    {
        if (s[i][mid]!=s[i][mid-1]) continue;
        ans.res-=merge(x.r[i],y.l[i]);
    }
    for (int i=1;i<=n;i++)
    {
        ans.l[i]=getfa(x.l[i]);
        ans.r[i]=getfa(y.r[i]);
    }
    return ans;
}

void build(int x,int l,int r)
{
    if (r-l==1)
    {
        tree[x].res=n;
        for (int i=1;i<=n;i++)
        {
            if (s[i][l]!=s[i-1][l]) cnt++;
            else tree[x].res--;
            tree[x].l[i]=tree[x].r[i]=cnt;
        }
    }
    else
    {
        int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid,r);
        tree[x]=pushup(tree[ls],tree[rs],mid);
    }
}

Tree query(int x,int tl,int tr,int l,int r)
{
    if (l<=tl && r>=tr) return tree[x];
    else
    {
        int mid=(tl+tr)>>1;
        if (r<=mid) return query(ls,tl,mid,l,r);
        if (l>=mid) return query(rs,mid,tr,l,r);
        return pushup(query(ls,tl,mid,l,r),query(rs,mid,tr,l,r),mid);
    }
}

#undef ls
#undef rs

signed main()
{
    n=read(); m=read(); q=read();
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) s[i][j]=read();
    build(1,1,m+1);
    while (q--)
    {
        a=read(); b=read();
        printf("%d\n",query(1,1,m+1,a,b+1).res);
    }
    return 0;
}