1018: [SHOI2008]堵塞的交通traffic

链接

分析：

　　用线段树维护区间的四个端点的联通情况，然后查询的时候，把所有覆盖到的区间合并起来即可。

　　六种情况左上到右上（左边到右边的情况）……，左上到左下（同一侧相互到达的情况）……

　　同一侧相互到达的情况，查询[l,r]是查的不完全。因为还有可能是先往左边走几步，下去，在走回来。这时候，查询一下[1,l]的情况，或起来即可。

代码：

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<cctype>

 #include<set>

 #include<vector>

 #include<queue>

 #include<map>

 #define fi(s) freopen(s,"r",stdin);

 #define fo(s) freopen(s,"w",stdout);

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 #define Root 1, n, 1

 #define lson l, mid, rt << 1

 #define rson mid + 1, r, rt << 1 | 1

 const int N = ;

 struct Node{

     bool l, r, s, x, a, b, t[];

     Node () {l = r = s = x = a = b = t[] = t[] = ; }

 }T[N << ];

 int n, A1, A2, B1, B2;

 Node operator + (const Node &p, const Node &q) {

     Node ans;

     ans.t[] = q.t[], ans.t[] = q.t[];

     if (p.l || (p.s && p.t[] && q.l && p.t[] && p.x)) ans.l = ;

     if (q.r || (q.s && p.t[] && p.r && p.t[] && q.x)) ans.r = ;

     if ((p.s && p.t[] && q.s) || (p.b && p.t[] && q.a)) ans.s = ;

     if ((p.x && p.t[] && q.x) || (p.a && p.t[] && q.b)) ans.x = ;

     if ((p.x && p.t[] && q.a) || (p.a && p.t[] && q.s)) ans.a = ;

     if ((p.s && p.t[] && q.b) || (p.b && p.t[] && q.x)) ans.b = ;

     return ans;

 }

 void build(int l,int r,int rt) {

     if (l == r) {

         T[rt].s = T[rt].x = ; return ;

     }

     int mid = (l + r) >> ;

     build(lson); build(rson);

     T[rt] = T[rt << ] + T[rt <<  | ];

 }

 void update1(int l,int r,int rt,int p,int opt) {

     if (l == r) {

         T[rt].t[A1 - ] = opt; return;

     }

     int mid = (l + r) >> ;

     if (p <= mid) update1(lson, p, opt);

     else update1(rson, p, opt);

     T[rt] = T[rt << ] + T[rt <<  | ];

 }

 void update2(int l,int r,int rt,int p,int opt) {

     if (l == r) {

         T[rt].l = T[rt].r = T[rt].a = T[rt].b = opt;

         return ;

     }

     int mid = (l + r) >> ;

     if (p <= mid) update2(lson, p, opt);

     else update2(rson, p, opt);

     T[rt] = T[rt << ] + T[rt <<  | ];

 }

 Node query(int l,int r,int rt,int L,int R) {

     if (L <= l && r <= R) {

         return T[rt];

     }

     int mid = (l + r) >> ;

     if (L > mid) return query(rson, L, R); // 注意这里的返回值，不能直接用一个ans来加

     else if (R <= mid) return query(lson, L, R);

     else return query(lson, L, R) + query(rson, L, R);

 }

 bool solve() {

     int L = query(Root, , B1).r;

     int R = query(Root, B2, n).l;

     Node now = query(Root, B1, B2);

     if (A1 == A2) {

         if ((A1 == ) && (now.s || (L && now.a) || (now.b && R) || (L && now.x && R))) return ; // A1的判断！！！

         if ((A1 == ) && (now.x || (L && now.b) || (now.a && R) || (L && now.s && R))) return ;

     } else {

         if ((A1 == ) && (now.b || (now.s && R) || (L && now.x) || (L && now.a && R))) return ;

         if ((A1 == ) && (now.a || (now.x && R) || (L && now.s) || (L && now.b && R))) return ;

     }

     return ;

 }

 int main() {

     n = read(); char opt[];

     build(Root);

     while (true) {

         scanf("%s", opt);

         if (opt[] == 'E') break;

         A1 = read(), B1 = read(), A2 = read(), B2 = read();

         if (B1 > B2) swap(A1, A2), swap(B1, B2);

         if (opt[] == 'A') puts(solve() ? "Y" : "N");

         else {

             if (B1 != B2) update1(Root, B1, opt[] == 'O' ?  : );

             else update2(Root, B1, opt[] == 'O' ?  : );

         }

     }

     return ;

 }