先把题目链接贴在这里喵~
http://main.edu.pl/en/archive/amppz/2013/baj
话说真是一道让我严重怀疑我的智商的好题目，
话说此题第一感觉。嗯？似乎离线做做就可以了喵？
诶呦我艹，这个和强制在线一样的感觉是怎么一回事啊！
然后我苦思良久，终于在我他喵的苦思冥想之下，发现了——
此题果然非我所能破~
但是看了题解后顿时表示这么多年书白读了TAT
首先原图是平面图，且仅有删边操作
我们维护原图G的对偶图G'的一个子图G''，这个子图的连通性对应了G中各个域(各个方块)的连通性
一开始没有边被删去， V''=V' ， E'=Ø ，说明各个域都不连通
然后每(在G中)删一条边，就在G''中加上对应的那条边
我们注意到现在只有加边的操作，可以用并查集维护所有域的连通性！
而且因为平面图的对偶图仍是平面图，平面图的子图仍是平面图
所以易得G''是平面图
【引理】
本傻装B系列
•平面图G''描述了平面图G删去若干条边后各域的连通性。
•则G''画到平面上后的每个域对应了G的一个新增的连通分量。
【推论】
•如果G中的一条边是G的桥，那么在G''中加入这条边的对应边将引入新的环。
•如果G中的一条边是G的桥，那么这条边的对应边的两端是联通的。
于是只要使用并查集维护各域的联通性，每次加边前询问两端是否联通就成功解决该题目了~
没看懂不要紧，其实我也不知道我在说什么，还是看图吧
1.现在有 9 个域，互相不练通
2.oh，我们删掉了一条边
3.然后 2 和 5 两个域就联通了
那么什么时候两个点不练通了呢？注意第 2 行第 3 个点
4.2 3 5 6域都是联通的
5.我们又要删去一条边，但是 2 3域已经联通了！这样就形成了一个环！
6.我们发现第 2 行第 3 个点和其他点都不连通了
其实脑补一下就知道，如果有两个点不连通，那么一个点的周围一定会有想围墙一样围起来的区域，而且该区域不存在连向外边的边
题目变一变就变成普及组水题了……
1 #include <cstdio> 2 const int size=2250225; 3 4 namespace IOspace 5 { 6 inline char getch() 7 { 8 register char ch; 9 do ch=getchar(); while (ch!='E' && ch!='N'); 10 return ch; 11 } 12 inline int getint() 13 { 14 register int num=0; 15 register char ch; 16 do ch=getchar(); while (ch<'0' || ch>'9'); 17 do num=num*10+ch-'0', ch=getchar(); while (ch>='0' && ch<='9'); 18 return num; 19 } 20 inline void putint(bool num) 21 { 22 if (num==0) printf("TAK "); 23 else printf("NIE "); 24 } 25 } 26 27 int n, k; 28 inline void swap(int & x, int & y) {int t=x; x=y; y=t;} 29 30 struct node 31 { 32 int x, y; 33 inline node() {} 34 inline node(int _x, int _y):x(_x), y(_y) {} 35 }; 36 inline int f(int x, int y) {if (x==0 || x==n || y==0 || y==n) return 0; return (x-1)*(n-1)+y;} 37 inline node getedge(); 38 39 int r[size]; 40 inline void prepare() {for (int i=0;i<n*n;i++) r[i]=i;} 41 int find(int x) {return r[x]==x?x:r[x]=find(r[x]);} 42 inline void merge(int x, int y) {x=find(x); y=find(y); r[x]=y;} 43 44 int main() 45 { 46 bool ans; 47 node T, N; 48 49 n=IOspace::getint(), k=IOspace::getint(); 50 prepare(); 51 ans=0; 52 for (int i=1;i<=k;i++) 53 { 54 T=getedge(); N=getedge(); 55 if (ans) T=N; 56 ans=find(T.x)==find(T.y); 57 IOspace::putint(ans); 58 merge(T.x, T.y); 59 } 60 61 return 0; 62 } 63 64 inline node getedge() 65 { 66 int x=IOspace::getint(), y=IOspace::getint(); 67 char c=IOspace::getch(); 68 if (c=='N') return node(f(x-1, y), f(x, y)); 69 if (c=='E') return node(f(x, y-1), f(x, y)); 70 }