题目描述
给出一张2*n的网格图，初始每条边都是不连通的。多次改变一条边的连通性或询问两个点是否连通。
输入
第一行只有一个整数C，表示网格的列数。接下来若干行，每行为一条交通信息，以单独的一行“Exit”作为结束。我们假设在一开始所有的道路都是堵塞的。我们保证 C小于等于100000，信息条数小于等于100000。
输出
对于每个查询，输出一个“Y”或“N”。
样例输入
2 Open 1 1 1 2 Open 1 2 2 2 Ask 1 1 2 2 Ask 2 1 2 2 Exit
样例输出
Y N
题解
线段树区间合并+STL-set
由于地图只有2*n，因此可以对于每一段格子维护其端点的连通性，即维护左上（下）与右上（下）的连通性。使用线段树区间合并很容易维护。
然后对于每个询问，如果不经过两点围成矩形区域以外的边的话，直接在线段树中查找即可。
如果经过矩形区域以外的边，那么一定是跨越行，并且显然是经过左（右）第一个能够跨越行的纵向边。因此可以使用set查前驱后继，此时再使用线段树查询即可。
时间复杂度$O(n\log n)$
#include#include #include #define N 100010#define lson l , mid , x << 1#define rson mid + 1 , r , x << 1 | 1using namespace std;set s;set ::iterator it;struct data{ bool v[2][2]; bool *operator[](int a) {return v[a];} data operator+(data a) { data ans; ans[0][0] = (v[0][0] && a[0][0]) || (v[0][1] && a[1][0]); ans[0][1] = (v[0][0] && a[0][1]) || (v[0][1] && a[1][1]); ans[1][0] = (v[1][0] && a[0][0]) || (v[1][1] && a[1][0]); ans[1][1] = (v[1][0] && a[0][1]) || (v[1][1] && a[1][1]); return ans; }}a[N << 2];bool px[N][2] , py[N];int n;char str[10];inline void pushup(int x){ a[x] = a[x << 1] + a[x << 1 | 1];}void fix(int p , int l , int r , int x){ if(l == r) { a[x][0][0] = (px[p][0]) || (py[p] && px[p][1] && py[p + 1]); a[x][0][1] = (py[p] && px[p][1]) || (px[p][0] && py[p + 1]); a[x][1][0] = (py[p] && px[p][0]) || (px[p][1] && py[p + 1]); a[x][1][1] = (px[p][1]) || (py[p] && px[p][0] && py[p + 1]); return; } int mid = (l + r) >> 1; if(p <= mid) fix(p , lson); else fix(p , rson); pushup(x);}data query(int b , int e , int l , int r , int x){ if(b > e) { data ans; ans[0][0] = ans[1][1] = 1; ans[0][1] = ans[1][0] = py[b]; return ans; } if(b <= l && r <= e) return a[x]; int mid = (l + r) >> 1; if(e <= mid) return query(b , e , lson); else if(b > mid) return query(b , e , rson); else return query(b , e , lson) + query(b , e , rson);}bool judge(int x1 , int y1 , int x2 , int y2){ if(y1 > y2) swap(x1 , x2) , swap(y1 , y2); if(query(y1 , y2 - 1 , 1 , n , 1)[x1][x2]) return 1; int pl = 0 , pr = 0; it = s.upper_bound(y1); if(it != s.begin()) pl = *--it; it = s.lower_bound(y2); if(it != s.end()) pr = *it; if(pl && query(pl , y1 - 1 , 1 , n , 1)[x1][x1] && query(pl , y2 - 1 , 1 , n , 1)[x1 ^ 1][x2]) return 1; if(pr && query(y1 , pr - 1 , 1 , n , 1)[x1][x2 ^ 1] && query(y2 , pr - 1 , 1 , n , 1)[x2][x2]) return 1; if(pl && pr && query(pl , y1 - 1 , 1 , n , 1)[x1][x1] && query(pl , pr - 1 , 1 , n , 1)[x1 ^ 1][x2 ^ 1] && query(y2 , pr - 1 , 1 , n , 1)[x2][x2]) return 1; return 0;}int main(){ int x1 , y1 , x2 , y2; scanf("%d" , &n) , n -- ; while(~scanf("%s" , str) && str[0] != 'E') { scanf("%d%d%d%d" , &x1 , &y1 , &x2 , &y2) , x1 -- , x2 -- ; if(str[0] != 'A') { if(x1 > x2) swap(x1 , x2); if(y1 > y2) swap(y1 , y2); if(x1 == x2) px[y1][x1] = (str[0] == 'O') , fix(y1 , 1 , n , 1); else { if(str[0] == 'O') s.insert(y1) , py[y1] = 1; else s.erase(y1) , py[y1] = 0; if(y1 > 1) fix(y1 - 1 , 1 , n , 1); if(y1 <= n) fix(y1 , 1 , n , 1); } } else if(judge(x1 , y1 , x2 , y2)) puts("Y"); else puts("N"); } return 0;}