[SDOI2013] 城市规划
题意：给你一个 \(6 \times n\) 的网格题，单点修改，询问区间联通块数，\(n \le 10^5\)。
解：看起来就很显然的一道题......线段树每个点用一个 ufs 维护连通性；
我为了方便思考把图转成横着的了。
写起来真是毒瘤......
重点在于：
\(\bullet\) 1、建立叶节点。
\(\bullet\) 2、合并两个子节点。
\(\bullet\) 3、把新的并查集的中间两列压掉。
第一步，这个就直接枚举 \(merge\) 就完事了。
第二步，把两个 2 列的子并查集复制到当前节点的 4 列的并查集上。注意右边那个并查集，\(fa\) 全部要加 \(2m\)，因为下标加了 \(2m\)。
然后枚举中间两列 \(merge\)。这样也做完了。
第三步，我们只要保留两边的两列即可。注意到有可能有两边元素的代表元在中间，我们使用左偏树技巧，切换代表元到它自己，注意 \(vis\) 也要变。
然后把两边的 \(vis\) 和 \(fa\) 复制一份出来，用以查询代表元。
然后把前两列 init，然后枚举每个元素，跟它的代表元 \(merge\)。注意这一步会对连通块总数 tot 造成改变，最后复原即可。
最后把前两列的 \(vis\) 和 \(lk\) 从复制的那里拿来用即可。
注意 \(vis\)（当前联通块是否有建筑物）要继承代表元的，\(lk\)（能否与两边连通）直接从对应下标继承，这两个不一样！
具体实现看代码吧......
#include<bits/stdc++.h>
using namespace std;
#define ck(x) ((x)=='|'||(x)=='+')
const int N=1e5+100;
const int M=24;
int n,m,q,x,y;
char c[2];
int exfa[M],exvis[M],exlk[M];
inline int read(){
char c=getchar();int f=1,x=0;
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int exfind(int x){
if(exfa[x]==x) return x;
else return exfa[x]=exfind(exfa[x]);
}
inline int trans(int x){
return x<m?x:x-(m<<1);
}
struct node{
int fa[M],tot;
bitset<M> lk,vis;
int find(int x){
if(fa[x]==x) return x;
else return fa[x]=find(fa[x]);
}
inline void merge(int x,int y){
int fx=find(x),fy=find(y);
if(fx==fy) return ;
fa[fy]=fx;
tot-=(vis[fx]&&vis[fy]);
if(vis[fy]) vis.set(fx);
return ;
}
node(){}
node(char *a){
tot=0;
for(int i(0);i<m;i++){
fa[i+m]=fa[i]=i;
if(a[i]=='O'){
vis.set(i);
vis.set(i+m);
lk.set(i);
lk.set(i+m);
++tot;
}else if(a[i]=='.'){
vis.reset(i);
vis.reset(i+m);
lk.reset(i);
lk.reset(i+m);
}else if(a[i]=='-'||a[i]=='+'){
vis.reset(i);
vis.reset(i+m);
lk.set(i);
lk.set(i+m);
}
}
for(int i(1);i<m;i++){
if(ck(a[i-1])&&ck(a[i])) merge(i-1,i);
else if((ck(a[i-1])&&a[i]=='O')||(ck(a[i])&&a[i-1]=='O')) merge(i-1,i);
else if(a[i]=='O'&&a[i-1]=='O') merge(i-1,i);
}
}
inline void update(){
for(int i(0);i<m;i++){
int t(find(i));
fa[i]=fa[t]=i;
vis[i]=vis[t];
t=find(i+3*m);
fa[i+3*m]=fa[t]=i+3*m;
vis[i+3*m]=vis[t];
}
memcpy(exfa,fa,sizeof(fa));
for(int i(0);i<m;i++){
exvis[i]=vis[i];
exvis[i+3*m]=vis[i+3*m];
exlk[i]=lk[i];
exlk[i+3*m]=lk[i+3*m];
}
int temp=tot;
for(int i(0);i<m;i++){
fa[i]=i;
fa[i+m]=i+m;
}
for(int i(0);i<m;i++){
merge(i,trans(exfind(i)));
merge(i+m,trans(exfind(i+3*m)));
}
for(int i(0);i<m;i++){
vis[i]=exvis[exfind(i)];
vis[i+m]=exvis[exfind(i+m*3)];
lk[i]=exlk[i];
lk[i+m]=exlk[i+m*3];
}
tot=temp;
return ;
}
inline node merge(const node &w)const{
node ans;
for(int i(0);i<m;i++){
ans.fa[i]=fa[i];
ans.lk[i]=lk[i];
ans.vis[i]=vis[i];
ans.fa[i+m]=fa[i+m];
ans.lk[i+m]=lk[i+m];
ans.vis[i+m]=vis[i+m];
ans.fa[i+2*m]=w.fa[i]+2*m;
ans.lk[i+2*m]=w.lk[i];
ans.vis[i+2*m]=w.vis[i];
ans.fa[i+3*m]=w.fa[i+m]+2*m;
ans.lk[i+3*m]=w.lk[i+m];
ans.vis[i+3*m]=w.vis[i+m];
}
ans.tot=tot+w.tot;
for(int i(0);i<m;i++){
if(ans.lk[i+m]&&ans.lk[i+2*m]){
ans.merge(i+m,i+2*m);
}
}
ans.update();;
return ans;
}
}tr[N<<2];
char str[N][6];
void build(int l,int r,int now){
if(l==r){
tr[now]=node(str[r]);
return ;
}
int mid=(l+r)>>1;
build(l,mid,now<<1);
build(mid+1,r,now<<1|1);
tr[now]=tr[now<<1].merge(tr[now<<1|1]);
return ;
}
void change(int p,int l,int r,int now){
if(l==r){
tr[now]=node(str[r]);
return ;
}
int mid=(l+r)>>1;
if(p<=mid) change(p,l,mid,now<<1);
else change(p,mid+1,r,now<<1|1);
tr[now]=tr[now<<1].merge(tr[now<<1|1]);
return ;
}
node get_sum(int x,int y,int l,int r,int now){
if(x<=l&&y>=r) return tr[now];
int mid=(l+r)>>1;
if(y<=mid) return get_sum(x,y,l,mid,now<<1);
if(mid<x) return get_sum(x,y,mid+1,r,now<<1|1);
node temp(get_sum(x,y,l,mid,now<<1));
temp=temp.merge(get_sum(x,y,mid+1,r,now<<1|1));
return temp;
}
signed main(){
n=read();m=read();
for(int i=1;i<=n;i++){
scanf("%s",str[i]);
for(int j=0;j<m;j++){
if(str[i][j]=='-') str[i][j]='|';
else if(str[i][j]=='|') str[i][j]='-';
}
}
build(1,n,1);
q=read();
while(q--){
scanf("%s",c);
x=read();y=read();
if(c[0]=='C'){
scanf("%s",c);
if(c[0]=='-') c[0]='|';
else if(c[0]=='|') c[0]='-';
str[x][y-1]=c[0];
change(x,1,n,1);
}else{
node temp=get_sum(x,y,1,n,1);
printf("%d\n",temp.tot);
}
}
return 0;
}
（ PS :一开始没开 O2 的时候 TLE 了，只有 50 分，吸氧以后才过的，希望哪位 dalao 可以找到更好的思路）