自动搬运

查看原文

来自洛谷，原作者为

	gongbangrui **

搬运于2025-08-24 21:47:29，当前版本为作者最后更新于2018-08-15 18:12:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解法：

题目有个条件，就是m<=6，于是启发我们可以按照行建立数据结构，由于列很少可以快速维护行与行之间的信息。稍加思考发现线段树是可行的。维护行与行之间的关系也很简单，只要通过并查集来实现，如果不会可以去做做[wc2005]双面棋盘这道题。

这题的一个细节是，如果只有道路的连通块是不能算进答案的，所以实现时加一个布尔数组判断这个连通块内是否有‘O’。这题的思维难度一般，主要考察实现能力和代码细心。。

最后还要orz Xietutu。。一开始连通的条件理解错，连暴力都wa了。后来是某大佬告诉我正确的理解。我太弱了...

AC代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=100003;
struct node
{
    int sum,u[7],d[7];
    bool avld[7],avlu[7];
}tree[maxn*4];
int n,m,fa[100],lab[100],cnt[100];
bool flag[100];
char a[maxn][7];
 
inline int get()
{
    int f=0,v=0;char ch;
    while(!isdigit(ch=getchar()))if(ch=='-')break;
    if(ch=='-')f=1;else v=ch-48;
    while(isdigit(ch=getchar()))v=v*10+ch-48;
    if(f==1)return -v;else return v;
}
inline void write(int x)
{
    int _=x,len=0,p[20];
    if(_<0)putchar('-'),_=-_;
    while(_)p[++len]=_%10,_/=10;
    if(!x)p[++len]=0;
    while(len)putchar(p[len--]+'0');
}
inline void writeln(int x)
{
    write(x);puts("");
}
inline bool check(const char &a,const char &b,const char &c) 
{
    return (a=='O'||a==c||a=='+')&&(b=='O'||b==c||b=='+');
}
inline void init(int p,int x)
{
    tree[p].sum=0;
    for(int i=1;i<=m;i++)tree[p].u[i]=tree[p].d[i]=tree[p].avld[i]=tree[p].avlu[i]=0;
    int tot=0;
    for(int i=1,j;i<=m;i++)
    {
        if(a[x][i]=='.')continue;
        bool avl=0;
        for(j=i;j<m&&check(a[x][j],a[x][j+1],'-');j++);
        for(int k=i;k<=j&&!avl;k++)avl|=a[x][k]=='O';
        ++tot;
        for(int k=i;k<=j;k++)tree[p].u[k]=tree[p].d[k]=tot,tree[p].avld[k]=tree[p].avlu[k]=avl;
        tree[p].sum+=int(avl);
        i=j;
    }
}
 
inline int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
 
inline void merge(node &x,const node &ls,const node &rs,const int &l,const int &r,const int &mid)
{
    x.sum=ls.sum+rs.sum;
    for(int i=1;i<=m;i++)x.u[i]=x.d[i]=x.avld[i]=x.avlu[i]=0;
    for(int i=1;i<=4*m;i++)fa[i]=i,lab[i]=0,flag[i]=0;
    for(int i=1;i<=m;i++)
    {
        if(ls.d[i])cnt[ls.d[i]]=ls.avld[i],flag[ls.d[i]]=1;
        if(rs.u[i])cnt[rs.u[i]+2*m]=rs.avlu[i],flag[rs.u[i]+2*m]=1;;
        if(ls.u[i])cnt[ls.u[i]]=ls.avlu[i];
        if(rs.d[i])cnt[rs.d[i]+2*m]=rs.avld[i];
    }
    for(int i=1;i<=m;i++)
    {
        if(!check(a[mid][i],a[mid+1][i],'|'))continue;
        int fx=getfa(ls.d[i]),fy=getfa(rs.u[i]+2*m);
        if(fx!=fy)fa[fx]=fy,cnt[fy]+=cnt[fx];
    }
    for(int i=1;i<=m*4;i++)
        if(flag[i]&&fa[i]==i&&cnt[i]>0)x.sum-=cnt[i]-1;
    for(int i=1,tot=0;i<=m;i++)
    {
        int fx;
        if(ls.u[i])
        {
            fx=getfa(ls.u[i]);
            if(!lab[fx])lab[fx]=++tot;
            x.u[i]=lab[fx],x.avlu[i]=cnt[fx];
        }
        if(rs.d[i])
        {
            fx=getfa(rs.d[i]+2*m);
            if(!lab[fx])lab[fx]=++tot;
            x.d[i]=lab[fx],x.avld[i]=cnt[fx];
        }
    }
}
 
inline void build(int p,int l,int r)
{
    if(l==r){init(p,l);return;}
    int mid=(l+r)/2;
    build(p*2,l,mid),build(p*2+1,mid+1,r);
    merge(tree[p],tree[p*2],tree[p*2+1],l,r,mid);
}
 
inline node ask(int p,int l,int r,int a,int b)
{
    if(a<=l&&r<=b)return tree[p];
    int mid=(l+r)/2;node res;
    if(b<=mid)res=ask(p*2,l,mid,a,b);
    else if(a>mid)res=ask(p*2+1,mid+1,r,a,b);
    else merge(res,ask(p*2,l,mid,a,mid),ask(p*2+1,mid+1,r,mid+1,b),a,b,mid);
    return res;
}
 
inline void modify(int p,int l,int r,int num)
{
    if(l==r){init(p,l);return;}
    int mid=(l+r)/2;
    if(num<=mid)modify(p*2,l,mid,num);else modify(p*2+1,mid+1,r,num);
    merge(tree[p],tree[p*2],tree[p*2+1],l,r,mid);
}
 
int main()
{
    n=get(),m=get();
    for(int i=1;i<=n;i++)scanf("%s",a[i]+1);
    build(1,1,n);
    int Q=get();
    while(Q--)
    {
        char ch;while(!isalpha(ch=getchar()));
        int x=get(),y=get();node res;
        if(ch=='C')
        {
            scanf(" %c",&a[x][y]);
            modify(1,1,n,x);
        }else res=ask(1,1,n,x,y),writeln(res.sum);
    }
    return 0;
}