bzoj 1018 堵塞的交通traffic 线段树

小咪咪 2023-08-17 17:22 115阅读 0赞

题意：有一个n \* 2的网格图，有3种操作：给两个相邻的点加上一条边，断开相邻的两个点连着的边，询问两个点的连通性。

思路：直接看博客就行了，[https://blog.csdn.net/roll\_keyboard/article/details/81185535][https_blog.csdn.net_roll_keyboard_article_details_81185535]，在纸上画一画来确定4个顶点之间的更新关系。有一个需要注意的细节是有可能通过绕远路的方式可以到达，所以需要考虑前面和后面的部分对询问区间的影响。

代码：

#include <bits/stdc++.h>
    #define ls (o << 1)
    #define rs (o << 1 | 1)
    using namespace std;
    const int maxn = 100010;
    struct node {
    	bool l, r, u, d, x1, x2, U, D; 
    };
    node tr[maxn * 4];
    node init() {
    	node ans;
    	ans.l = ans.r = ans.D = ans.U = ans.x1 = ans.x2 = 0;
    	ans.u = ans.d = 1;
    	return ans;
    }
    node merge(node a1, node a2) {
    	node ans;
    	ans.l = (a1.l | (a1.u & a1.U & a2.l & a1.D & a1.d));
    	ans.r = (a2.r | (a2.u & a1.U & a1.r & a1.D & a1.d));
    	ans.u = ((a1.u & a1.U & a2.u) | (a1.x1 & a1.D & a2.x2));
    	ans.d = ((a1.d & a1.D & a2.d) | (a1.x2 & a1.U & a2.x1));
    	ans.x1 = ((a1.u & a1.U & a2.x1) | (a1.x1 & a1.D & a2.d));
    	ans.x2 = ((a1.x2 & a1.U & a2.u) | (a1.d & a1.D & a2.x2));
    	ans.U = a2.U;
    	ans.D = a2.D;
    	return ans; 
    }
    void build(int o, int l, int r) {
    	if(l == r) {
    		tr[o] = init();
    		return;
    	}
    	int mid = (l + r) >> 1;
    	build(ls, l, mid);
    	build(rs, mid + 1, r);
    	tr[o] = merge(tr[ls], tr[rs]);
    }
    void update(int o, int l, int r, int p, int type) {
    	if(l == r) {
    		if(type >> 2) {
    			tr[o].l = tr[o].r = tr[o].x1 = tr[o].x2 = (type & 1);
    			return;	
    		} else if (type >> 1) {
    			tr[o].U = (type & 1);
    		} else {
    			tr[o].D = (type & 1);
    		}
    		return; 
    	}
    	int mid = (l + r) >> 1;
    	if(p <= mid) update(ls, l, mid, p, type);
    	else update(rs, mid + 1, r, p, type);
    	tr[o] = merge(tr[ls], tr[rs]);
    }
    node query(int o, int l, int r, int ql, int qr) {
    	if(l >= ql && r <= qr) {
    		return tr[o];
    	}
    	int mid = (l + r) >> 1;
    	node ans = init();
    	ans.U = ans.D = 1;
    	if(ql <= mid) ans = merge(ans, query(ls, l, mid, ql, qr));
    	if(qr > mid) ans = merge(ans, query(rs, mid + 1, r, ql, qr));
    	return ans;
    }
    void out(bool flag) {
    	if(flag) printf("Y\n");
    	else printf("N\n");
    }
    char s[10];
    int main() {
    	int n;
    	scanf("%d", &n);
    	int x1, y1, x2, y2;
    	build(1, 1, n);
    	while(1) {
    		scanf("%s", s + 1);
    		if(s[1] == 'E') break;
    		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    		if(y1 > y2) {
    			swap(x1, x2);
    			swap(y1, y2); 
    		}
    		if(s[1] == 'A') {
    			node ans1, ans2, ans3;
    			if(y1 > 1) ans1 = query(1, 1, n, 1, y1 - 1);
    			ans2 = query(1, 1, n, y1, y2);
    			if(y2 < n) ans3 = query(1, 1, n, y2 + 1, n);
    			if(y1 > 1 && (ans1.r && ans1.U && ans1.D)) {
    				ans2.l |= 1;
    				ans2.x1 |= (ans2.l & ans2.d);
    				ans2.x2 |= (ans2.l & ans2.u);
    				ans2.d |= (ans2.x1 & ans2.l);
    				ans2.u |= (ans2.l & ans2.x2);
    			}
    			if(y2 < n && (ans2.U && ans3.l && ans2.D)) {
    				ans2.r |= 1;
    				ans2.x1 |= (ans2.u & ans2.r);
    				ans2.x2 |= (ans2.d & ans2.r);
    				ans2.d |= (ans2.x2 & ans2.r);
    				ans2.u |= (ans2.x1 & ans2.r);
    			}
    			if(x1 == 1 && x2 == 1) {
    				out(ans2.u);
    			} else if(x1 == 1 && x2 == 2) {
    				out(ans2.x1);
    			} else if(x1 == 2 && x2 == 1) {
    				out(ans2.x2);
    			} else {
    				out(ans2.d);
    			}
    		} else {
    			int type = 0;
    			if(y1 == y2) {
    				type |= (1 << 2);
    				if(s[1] == 'O') type |= 1;
    			} else {
    				if(x1 == 1) type |= (1 << 1);
    				if(s[1] == 'O') type |= 1;
    			}
    			update(1, 1, n, y1, type);
    		}
    	}
    }

转载于:https://www.cnblogs.com/pkgunboat/p/11445883.html

[https_blog.csdn.net_roll_keyboard_article_details_81185535]: https://blog.csdn.net/roll_keyboard/article/details/81185535