Codeforces811E Vladik and Entertaining Flags

本文移植自个人的原博客（原文）

题目链接

Vladik and Entertaining Flags

题目描述

题解

考虑到$n$的范围较小，可以直接通过并查集暴力每一列的联通性，每次询问通过归并查询，可以先用线段树预处理以降低时间复杂度。

$ls，rs$数组表示当前需要合并的$[l,r]$的左右两边的连通性，归并时向上更新，$l,r$数组表示线段树当前节点的$[l,r]$的连通性，需要提前预处理。对于合并操作，考虑需要合并的两个区间，连通性改变的部分只有两个区间相邻的部分，同样可以通过并查集暴力求解。

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 5e5+1;
int a[13][N],l[N*2][13],sum[N*2],r[N*2][13],rs[11],ls[11],n,m,cnt,q;
int f[13*N*2],flag;
int gf(int x){return f[x]==x?x:f[x]=gf(f[x]);}
int update(int ll, int rr,int x)
{
    int ls=x*2,rs=x*2+1;
    sum[x]=sum[ls]+sum[rs];
    for(int i=1;i<=n;++i)
    {
        f[l[ls][i]]=l[ls][i];
        f[r[rs][i]]=r[rs][i];
        f[l[rs][i]]=l[rs][i];
        f[r[ls][i]]=r[ls][i];
    }
    int mid=ll+rr>>1;
    for(int i=1;i<=n;++i)
    if(a[i][mid]==a[i][mid+1])
    {
        int t1=gf(l[rs][i]),t2=gf(r[ls][i]);
        if(t1!=t2)
        {
            f[t1]=t2;
            sum[x]--;
        }
    }
    for(int i=1;i<=n;++i)
    l[x][i]=gf(l[ls][i]),r[x][i]=gf(r[rs][i]);
    return 0;
}


int build(int ll,int rr,int x)
{
    if(ll==rr)
    {
        for(int i=1;i<=n;++i)
        if(a[i][ll]==a[i-1][ll])l[x][i]=r[x][i]=l[x][i-1];
        else    l[x][i]=r[x][i]=++cnt,sum[x]++;
        return 0;
    }
    int mid=ll+rr>>1;
    build(ll,mid,x*2);build(mid+1,rr,x*2+1);
    update(ll,rr,x);
}

int mergesort(int ll,int rr,int x,int y,int now)
{
    int lss=now*2,rss=now*2+1;
    if(x<=ll&&rr<=y)
    {
        if(flag)
        {
            flag=0;
            for(int i=1;i<=n;++i)
            ls[i]=l[now][i],rs[i]=r[now][i];
            return sum[now];
        }
    else
    {
        int ret=sum[now];
        for(int i=1;i<=n;++i)
        {
            f[ls[i]]=ls[i];
            f[rs[i]]=rs[i];
            f[l[now][i]]=l[now][i];
            f[r[now][i]]=r[now][i];
        }
        for(int i=1;i<=n;++i)
        {
            if(a[i][ll]==a[i][ll-1])
            {
                int t1=gf(rs[i]),t2=gf(l[now][i]);
                if(t1!=t2)
                {
                    f[t2]=t1;
                    ret--;
                }
            }
        }
        for(int i=1;i<=n;++i)
        ls[i]=gf(ls[i]),rs[i]=gf(r[now][i]);
        return ret;
    }
    }
    int ret=0;
    int mid=ll+rr>>1;
    if(x<=mid) ret+=mergesort(ll,mid,x,y,now*2);
    if(mid<y)    ret+=mergesort(mid+1,rr,x,y,now*2+1);
    return ret;
}

int main()
{
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;++i)
    for(int t=1;t<=m;++t)
    scanf("%d",&a[i][t]);
    build(1,m,1);
    for(int i=1,ll,rr;i<=q;++i)
    {
        scanf("%d%d",&ll,&rr);
        flag=1;
        printf("%d\n",mergesort(1,m,ll,rr,1));
    }
}