传送门 一道蛋疼的线段树。 发现m很小，于是我们按照横坐标建线段树。然后用并查集维护上下2*m个节点的连通性。 然后这题略卡内存。
#include<cstring> #include<cmath> #include<cstdio> #include<iostream> #include<cstdlib> #include<algorithm>#define N 100005using namespace std;char ch[10];int n,m,mp[N][10],x,y,f[30],tag[30],v[30],q;int get(int x){return f[x]==x?x:f[x]=get(f[x]);}struct node{ int f[14],tag[14],l,r,sum; int get(int x){return x==f[x]?x:f[x]=get(f[x]);} void make(){ int p=l; sum=0; for (int i=1;i<=2*m;i++) f[i]=i,tag[i]=0; for (int i=1;i<=m;i++) if (mp[p][i]==4) tag[i]=1,sum++; for (int i=1;i<=m;i++) if (mp[p][i]>1){ if (i!=1&&mp[p][i-1]>1){ int x=get(i),y=get(i-1); if (x!=y){ f[y]=x; if (tag[x]&&tag[y]) sum--; else if (tag[y]) tag[x]=1; } } if (i!=m&&mp[p][i+1]>1){ int x=get(i),y=get(i+1); if (x!=y){ f[y]=x; if (tag[x]&&tag[y]) sum--; else if (tag[y]) tag[x]=1; } } } for (int i=1;i<=m;i++) f[i+m]=f[i]; }}t[N*4];node merge(node x,node y){ node tmp; memset(tmp.tag,0,sizeof(tmp.tag)); tmp.l=x.l; tmp.r=y.r; tmp.sum=x.sum+y.sum; for (int i=1;i<=2*m;i++) f[i]=x.f[i],tag[i]=x.tag[i]; for (int i=1;i<=2*m;i++) f[i+2*m]=y.f[i]+2*m,tag[i+2*m]=y.tag[i]; int p=x.r,q=p+1; for (int i=1;i<=m;i++) if (mp[p][i]!=0&&mp[p][i]!=2&&mp[q][i]!=0&&mp[q][i]!=2){ int x=get(m+i),y=get(m*2+i); if (x!=y){ f[x]=y; if (tag[x]&&tag[y]) tmp.sum--; else if (tag[x]) tag[y]=1; } } memset(v,0,sizeof(v)); for (int i=1;i<=m;i++){ int x=get(i); if (!v[x]) v[x]=i,tmp.tag[i]=tag[x]; x=get(i+3*m); if (!v[x]) v[x]=i+m,tmp.tag[i+m]=tag[x]; } for (int i=1;i<=m;i++){ tmp.f[i]=v[get(i)]; tmp.f[i+m]=v[get(i+3*m)]; } return tmp;}void build(int x,int l,int r){ t[x].l=l,t[x].r=r; if (l==r){ t[x].make(); return; } int mid=(l+r)/2; build(x*2,l,mid); build(x*2+1,mid+1,r); t[x]=merge(t[x*2],t[x*2+1]);}void rebuild(int x,int y){ int l=t[x].l,r=t[x].r,mid=(l+r)/2; if (l==r){ t[x].make(); return; } if (y<=mid) rebuild(x*2,y); else rebuild(x*2+1,y); t[x]=merge(t[x*2],t[x*2+1]);}node ask(int x,int a,int b){ int l=t[x].l,r=t[x].r,mid=(l+r)/2; if (l==a&&r==b) return t[x]; if (b<=mid) return ask(x*2,a,b); if (a>mid) return ask(x*2+1,a,b); return merge(ask(x*2,a,mid),ask(x*2+1,mid+1,b));}inline int change(char ch){ if (ch=='.') return 0; if (ch=='|') return 1; if (ch=='-') return 2; if (ch=='+') return 3; if (ch=='O') return 4;}int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=n;i++){ scanf("%s",ch+1); for (int j=1;j<=m;j++) mp[i][j]=change(ch[j]); } build(1,1,n); scanf("%d",&q); for (int i=1;i<=q;i++){ scanf("%s",ch); if (ch[0]=='Q'){ scanf("%d%d",&x,&y); PRintf("%d/n",ask(1,x,y).sum); } else{ scanf("%d%d%s",&x,&y,ch); mp[x][y]=change(ch[0]); rebuild(1,x); } }}新闻热点
疑难解答
