题解 P4246 【[SHOI2008]堵塞的交通】
看到题解里线段树合并结点的做法都是
大力讨论联通情况
我就很不爽。。为什么不上
我们在树上每个节点开并查集维护连通性，代替那一堆数组和变量什么的。
并查集做法的优点在于
-
你能无脑合并，因为不需要考虑
\color{red}\text{连通性和先后顺序之间的一堆影响} ，所以调试的时候根本不用操心最麻烦的节点合并部分 -
最后查答案也是无脑合并然后
Find()一下就好了 -
要维护的变量很少。
合并代码也相对简洁←情况其实非常多
不过一句题外话，我写的还是挺长的，也许是我变量名太长的缘故？或者并查集这种写法要讨论的情况本身就比开一堆变量那个要多??
制表符万岁！
我是按照横向道路建的树，维护的区间长度是
┌─┬─┬─┬─┬─┐
│1│2│3│4│5│ n=6
└─┴─┴─┴─┴─┘对于一个格子，编号如下:
1─2
│ │
3─4更新的时候，如果是横向更新，那需要更新对应的一个叶子。如果竖向的那需要更新夹起它的左右两个叶子。
竖向更新要照顾 L R 两个叶子。
┌─┬─┐
│L│R│
└─┴─┘然后询问的时候要先看在偏左的询问点能不能通过向左走的方式更新纵向上的连通性，然后偏右的询问点也同理，类似于这图：
r1=1 c1=3
r2=2 c2=5
┌─────┐
│ |
│ ┌─┬─○─┬─┬─┐
│ │1│2│3│4│5│
│ └─┴─┴─┴─○─┘
│ ↑
└─────┘
还有就是合并的时候要把左右两块合到一起，这个时候在中间要枚举好几种走法，然后就没啥可讲的了。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#define ll long long
using namespace std;
int n,m,conn[100010][4];
template<typename int_t>
void readx(int_t& x)
{
x=0; int_t k=1; char ch=0;
while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
x*=k;
}
int Find(int e,int ds[])
{
if (e!=ds[e]) ds[e]=Find(ds[e],ds);
return ds[e];
}
void Merge(int a,int b,int ds[])
{
ds[Find(b,ds)]=Find(a,ds);
}
namespace SGT
{
#define LCH (inx<<1)
#define RCH (inx<<1|1)
struct Seg_Tree
{
int l,r,mid;
int ds[6];
}tree[400010];
int lx,rx;
Seg_Tree Update(Seg_Tree A,Seg_Tree B)
{
Seg_Tree C;
C.l=A.l; C.r=B.r; C.mid=(A.l+B.r)>>1;
for (int i=1;i<=4;i++) C.ds[i]=i;
if (Find(1,A.ds)==Find(2,A.ds)) C.ds[2]=1;
if (Find(3,B.ds)==Find(4,B.ds)) C.ds[4]=3;
for (int i=1;i<=2;i++)
for (int j=3;j<=4;j++) if (Find(i,A.ds)==Find(j,A.ds))
for (int k=3;k<=4;k++) if (Find(j-2,B.ds)==Find(k,B.ds))
Merge(i,k,C.ds);
return C;
}
void BuildTree(int inx,int lxx,int rxx)
{
tree[inx].l=lxx; tree[inx].r=rxx;
tree[inx].mid=(lxx+rxx)>>1;
for (int i=1;i<=4;i++) tree[inx].ds[i]=i;
if (lxx==rxx) return;
BuildTree(LCH,lxx,tree[inx].mid);
BuildTree(RCH,tree[inx].mid+1,rxx);
}
void Upd(int inx)
{
if (tree[inx].l==lx && tree[inx].r==lx)
{
memset(tree[inx].ds,0,sizeof(tree[inx].ds));
for (int i=1;i<=4;i++) tree[inx].ds[i]=i;
if (conn[lx][1]) Merge(1,3,tree[inx].ds);
if (conn[lx][2]) Merge(2,4,tree[inx].ds);
if (conn[lx][3]) Merge(1,2,tree[inx].ds);
if (conn[lx+1][3]) Merge(3,4,tree[inx].ds);
return;
}
if (lx<=tree[inx].mid) Upd(LCH);
else Upd(RCH);
tree[inx]=Update(tree[LCH],tree[RCH]);
}
Seg_Tree Qry(int inx)
{
if (tree[inx].l>=lx && tree[inx].r<=rx) return tree[inx];
if (lx>tree[inx].mid) return Qry(RCH);
else if (rx<=tree[inx].mid) return Qry(LCH);
else return Update(Qry(LCH),Qry(RCH));
}
#undef LCH
#undef RCH
};
char cmd[110];
int main()
{
readx(n); SGT::BuildTree(1,1,n-1);
int c1,r1,c2,r2;
while (1)
{
scanf("%s",cmd+1);
if (cmd[1]=='E') return 0;
readx(r1); readx(c1); readx(r2); readx(c2);
if (cmd[1]=='A')
{
SGT::Seg_Tree tmp,tmp2;
if (c1==c2)
{
if (conn[c1][3]) { printf("Y\n"); continue; }
if (c1>1)
{
SGT::lx=1; SGT::rx=c1-1; tmp=SGT::Qry(1);
if (Find(3,tmp.ds)==Find(4,tmp.ds)) { printf("Y\n"); continue; }
}
if (c1<n)
{
SGT::lx=c1; SGT::rx=n-1; tmp=SGT::Qry(1);
if (Find(1,tmp.ds)==Find(2,tmp.ds)) { printf("Y\n"); continue; }
}
printf("N\n");
}
else
{
SGT::lx=min(c1,c2); SGT::rx=max(c1,c2)-1; tmp=SGT::Qry(1);
if (min(c1,c2)>1)
{
SGT::lx=1; SGT::rx=min(c1,c2)-1; tmp2=SGT::Qry(1);
if (Find(3,tmp2.ds)==Find(4,tmp2.ds)) Merge(1,2,tmp.ds);
}
if (max(c1,c2)<n)
{
SGT::lx=max(c1,c2); SGT::rx=n-1; tmp2=SGT::Qry(1);
if (Find(1,tmp2.ds)==Find(2,tmp2.ds)) Merge(3,4,tmp.ds);
}
if (c1<c2) r2+=2;
else r1+=2;
printf("%c\n",(Find(r1,tmp.ds)==Find(r2,tmp.ds))?'Y':'N');
}
}
else
{
if (c1==c2)
{
conn[c1][3]=(cmd[1]=='O');
if (c1>1) { SGT::lx=c1-1; SGT::Upd(1); }
if (c1<n) { SGT::lx=c1; SGT::Upd(1); }
}
else
{
conn[min(c1,c2)][r1]=(cmd[1]=='O');
SGT::lx=min(c1,c2); SGT::Upd(1);
}
}
}
}