【bzoj1018】堵塞的交通
题意
一个\(2*n\)的格子，相邻格子之间有一条道路。初始时道路是不通的。
\(C\)个操作，每个操作为三种中的一种：（1）某条道路连起来；（2）某条道路断开；（3）询问某两个格子是否相连。
数据范围：\(C\leq 100000\)
分析
这的确是一道好题。
不仅体现在思想的巧妙，而且体现在其一题多解。
参阅了百度前两页的题解，有所感想。
思路1：线段树
前人之述备矣。
用线段树维护区间内的信息：
\(a1[2][2]\)：a1[i][j]表示左端点的\(i\)到右端点的\(j\)是否联通；
\(a2[2]\)：a2[i]表示左或者右端点的上下是否联通；
还需要用到中点的信息\(b[2]\)：mid与mid+1是否联通，来完成合并。
注意是块内合并。
最后的询问才考虑到块外的情况。
时间复杂度：\(O(n\log n)\)
一份被我加了注释的代码 from invoid的题解
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 800000 + 10;
char s[20]; //操作
int x1,x2,y1,y2,c;
struct Segtree {
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define root 1
struct Status {
int a1[2][2],a2[2];
//a1表示左右断电联通情况，a2表示左右端点分别上下联通情况
}s[maxn];
bool b[maxn][2];
int l[maxn],r[maxn],m[maxn]; //l[x]：左端点 r[x]：右端点 m[x]：中点
Status update(Status s1,Status s2,bool b[]) { //左态，右态，中间态
Status res;
for(int i=0;i<=1;i++)
for(int j=0;j<=1;j++)
res.a1[i][j]=s1.a1[i][0] && b[0] && s2.a1[0][j] || s1.a1[i][1] && b[1] && s2.a1[1][j];
//基本联通，此时s1.a1已经包括了连出去的情况
res.a2[0]=s1.a2[0] || s1.a1[0][0] && b[0] && s2.a2[0] && b[1] && s1.a1[1][1];
res.a2[1]=s2.a2[1] || s2.a1[0][0] && b[0] && s1.a2[1] && b[1] && s2.a1[1][1];
//弄清一个误区：s[i]指表示[l,r]中的情况，最后处理答案的时候才考虑连到外面的情况
return res;
}
Status access (int x,int y1,int y2) {
if(y1<=l[x] && r[x]<=y2) return s[x];
else if(y2<=m[x]) return access(lc(x),y1,y2);
else if(y1>m[x]) return access(rc(x),y1,y2);
else return update(access(lc(x),y1,y2),access(rc(x),y1,y2),b[x]);
//access，b[x]为中间态
}
void change(bool k,int x,int x1,int y1,int x2,int y2) {
if(x1==x2 && y1==m[x]) { //同一行相邻两个
b[x][x1]=k; //x的mid到mid+1的连通性为k
s[x]=update(s[lc(x)],s[rc(x)],b[x]); //update
}
else if(l[x]==r[x]) //上下联通
s[x].a1[0][1]=s[x].a1[1][0]=s[x].a2[0]=s[x].a2[1]=k; //都是k
else {
change(k,y2<=m[x]?lc(x):rc(x),x1,y1,x2,y2); //递归
s[x]=update(s[lc(x)],s[rc(x)],b[x]); //update
}
}
void ask(int x1,int y1,int x2,int y2) {
Status left=access(root,1,y1), //1到y1
right=access(root,y2,c), //y2到c
mid=access(root,y1,y2); //y1到y2
bool res=false;
for(int i=0;i<=1;i++)
for(int j=0;j<=1;j++)
if(mid.a1[i][j]&&(i==x1||left.a2[1])&&(j==x2||right.a2[0])) {
//若mid[i][j]联通，i=x1或左联通，j=x2或右联通，则res=1
res=true; break;
}
printf(res?"Y\n":"N\n"); //返回res
}
void build(int x,int y1,int y2) {
l[x]=y1,r[x]=y2,m[x]=(l[x]+r[x])>>1;
if(y1==y2)
s[x].a1[0][0]=s[x].a1[1][1]=true;
else {
build(lc(x),y1,m[x]);
build(rc(x),m[x]+1,y2);
}
}
//连通
}seg;
int main() {
scanf("%d",&c);
seg.build(1,1,c);
while(1) {
scanf("%s",s);
if(s[0]=='E') break;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
--x1; --x2; //从0开始
if(y1>y2) {
swap(x1,x2);
swap(y1,y2);
}
//y1在前，y2在后
if(s[0]=='O') seg.change(1,1,x1,y1,x2,y2); //增边
else if(s[0]=='C') seg.change(0,1,x1,y1,x2,y2); //删边
else seg.ask(x1,y1,x2,y2); //查连
}
return 0;
}思路2：分块+并查集
http://blog.csdn.net/cjk_cjk/article/details/43489473
并查集有一定的局限性：只支持快速合并，不支持快速删除。
所以我们打算直接合并+初始化，而不使用删除。
但是初始化的速度较慢，所以我们考虑分块，对于询问只需要合并各个块即可。
根据平衡规划的思想，我们要是的初始化的速度尽可能快，而且块间的合并尽可能快，所以我们取\(O(\sqrt n)\)分一块。
Open：在同一块中就维护并查集，在不同块互相连通就用一个link数组记录
Close：在同一块中就把块中元素的fa[]全部重新计算，在不同块中直接把link赋零
Ask：判断A及能到达的4个顶点，再递归4个顶点到其他块的顶点，看顶点与B是否连通
时间复杂度：\(O(n\sqrt n)\)
思路3：定期重建 + [按秩合并 & 路径压缩]并查集
离线处理。
并查集有一定的局限性：只支持快速合并，不支持快速删除，但是按秩合并的并查集可以逐个删除。
所以我们打算直接合并+顺序撤除。
按照操作顺序，每\(\sqrt c\)个就分一次块。
每次处理出块前的并查集，然后按秩合并处理块内的询问，然后每次再撤销回块的初始状态。
时间复杂度：\(O(n\sqrt n\log n)\)
思路4：线段树+并查集
http://www.cnblogs.com/ccz181078/p/5346077.html
离线处理。
将每条存在的边的按存在时间插入到线段树中，对线段dfs一次，用按秩合并、支持撤销的并查集维护连通性并回答询问。
此方法适用于离线的图连通性维护。
真的是一种很优美的想法啊。
时间复杂度：\(O(n\log^2 n)\)
小结
（1）线段树的一些理解
①线段树的本质在于维护区间内的信息，假如要维护区间外的信息，正如开始我的想法，或许能够实现，但是未必好些，而且通常也可以转化为区间内信息的维护。
②线段树通常能够维护区间的连通性
（2）并查集的一些理解
并查集能支持快速合并，快速查询，前提：一个条件就可以导致一次合并。
对于删除，通常可以做这样的优化：
①转化为初始化+合并，通过平衡规划（按位置分块等）优化
②转化为按顺序合并，按顺序删除，这样可以通过按秩合并来实现，通过平衡规划（按操作顺序分块）或者回溯（本题线段树回溯）优化
（3）离线处理的一些方法总结
可以使用离线的前提：多个操作
特殊化：多个询问
下面列举一些方法，并举一些例子。
①回代法
bzoj1015
②按照操作顺序分块，定期重建
本题bzoj1018
③莫队算法
小Z的袜子
④确定左端点，移动右端点
HH的项链
⑤单调性，two pointer
noip2016Day1T2：树剖+树状数组
⑥cdq分治
bzoj简单题
⑦快速覆盖区间，从前往后遍历
本题bzoj1018，用线段树按照操作时间插入边，然后遍历线段树，访问每个时间（叶子节点）
能用到离线处理的远远不止这些。
只是积累一点经验罢了。
毕竟我不是一些可能存在的大神。
说什么劳资纯刷题就可以虐爆你。。