题解：P3300 [SDOI2013] 城市规划

· · 题解

思路

考虑线段树，每个节点维护最上面一行和最下面一行的连通块标号和有无 O，合并的时候考虑把左儿子最下面一行和右儿子最上面一行拉出来，用一个并查集维护连通性，最后把合并成功的联通块的贡献减掉就行了。

代码

#include<bits/stdc++.h>
using namespace std;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//char buf[1<<23],*p1=buf,*p2=buf;
int read(){char c=getchar();int p=0,flg=1;while(c<'0'||c>'9'){if(c=='-') flg=-1;c=getchar();}while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}return p*flg;}
int n,m,q,fa[30],siz[30],vis[30];char mp[100010][10];
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) return ;fa[x]=y;siz[y]+=siz[x];}
struct Info{
    int sum,id[10],_id[10],flg[10],_flg[10],U,D;
    Info(){sum=U=D=0;for(int i=1;i<=m;i++) id[i]=_id[i]=flg[i]=_flg[i]=0;}
    Info operator+(Info x){
        Info res;res.sum=sum+x.sum;res.U=U;res.D=x.D;
        for(int i=1;i<=m<<2;i++) fa[i]=i,siz[i]=vis[i]=0;
        for(int i=1;i<=m;i++){if(id[i]) siz[id[i]]=flg[i];if(_id[i]) siz[_id[i]]=_flg[i];if(x.id[i]) siz[x.id[i]+(m<<1)]=x.flg[i];if(x._id[i]) siz[x._id[i]+(m<<1)]=x._flg[i];}
        for(int i=1;i<=m;i++) if((mp[D][i]=='O'||mp[D][i]=='|'||mp[D][i]=='+')&&(mp[x.U][i]=='O'||mp[x.U][i]=='|'||mp[x.U][i]=='+')) merge(_id[i],x.id[i]+(m<<1));
        for(int i=1;i<=m<<2;i++) if(find(i)==i&&siz[i]) res.sum-=siz[i]-1;
        for(int i=1,cnt=0;i<=m;i++){
            if(id[i]){int u=find(id[i]);if(!vis[u]) vis[u]=++cnt;res.id[i]=vis[u];res.flg[i]=siz[u]>0;}
            if(x._id[i]){int u=find(x._id[i]+(m<<1));if(!vis[u]) vis[u]=++cnt;res._id[i]=vis[u];res._flg[i]=siz[u]>0;}
        }return res;
    }
};
struct seg{int l,r;Info x;}t[400010];
#define lson now<<1
#define rson now<<1|1
void build(int now,int l,int r){
    t[now]={l,r};if(l==r){
        t[now].x.U=t[now].x.D=l;for(int i=1,cnt=0;i<=m;i++) if(mp[l][i]^'.'){
            int j=i,f=(mp[l][i]=='O');while(j+1<=m&&(mp[l][j]=='O'||mp[l][j]=='-'||mp[l][j]=='+')&&(mp[l][j+1]=='O'||mp[l][j+1]=='-'||mp[l][j+1]=='+')) j++,f|=(mp[l][j]=='O');
            cnt++;for(int k=i;k<=j;k++) t[now].x.id[k]=t[now].x._id[k]=cnt,t[now].x.flg[k]=t[now].x._flg[k]=f;t[now].x.sum+=f;i=j;
        }return ;
    }int mid=(l+r)>>1;build(lson,l,mid);build(rson,mid+1,r);t[now].x=t[lson].x+t[rson].x;

}
void modify(int now,int x){
    if(t[now].l==t[now].r){
        for(int i=1;i<=m;i++) t[now].x=Info();t[now].x.U=t[now].x.D=x;for(int i=1,cnt=0;i<=m;i++) if(mp[x][i]^'.'){
            int j=i,f=(mp[x][i]=='O');while(j+1<=m&&(mp[x][j]=='O'||mp[x][j]=='-'||mp[x][j]=='+')&&(mp[x][j+1]=='O'||mp[x][j+1]=='-'||mp[x][j+1]=='+')) j++,f|=(mp[x][j]=='O');
            cnt++;for(int k=i;k<=j;k++) t[now].x.id[k]=t[now].x._id[k]=cnt,t[now].x.flg[k]=t[now].x._flg[k]=f;t[now].x.sum+=f;i=j;
        }return ;
    }int mid=(t[now].l+t[now].r)>>1;if(x<=mid) modify(lson,x);else modify(rson,x);t[now].x=t[lson].x+t[rson].x;
}
Info query(int now,int l,int r){
    if(l<=t[now].l&&t[now].r<=r) return t[now].x;
    int mid=(t[now].l+t[now].r)>>1;if(r<=mid) return query(lson,l,r);if(mid<l) return query(rson,l,r);return query(lson,l,r)+query(rson,l,r);
}
signed main(){
    n=read();m=read();for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>mp[i][j];build(1,1,n);
    q=read();while(q--){char opt;cin>>opt;int x=read(),y=read();if(opt=='C'){cin>>mp[x][y];modify(1,x);}else cout<<query(1,x,y).sum<<'\n';}
    return 0;
}