题目地址：洛谷：【P4246】[SHOI2008]堵塞的交通 – 洛谷、BZOJ：Problem 1018. — [SHOI2008]堵塞的交通traffic

题目描述

有一天，由于某种穿越现象作用，你来到了传说中的小人国。小人国的布局非常奇特，整个国家的交通系统可以被看成是一个2行C列的矩形网格，网格上的每个点代表一个城市，相邻的城市之间有一条道路，所以总共有2C个城市和3C-2条道路。

小人国的交通状况非常槽糕。有的时候由于交通堵塞，两座城市之间的道路会变得不连通，直到拥堵解决，道路才会恢复畅通。初来咋到的你决心毛遂自荐到交通部某份差事，部长听说你来自一个科技高度发达的世界，喜出望外地要求你编写一个查询应答系统，以挽救已经病入膏肓的小人国交通系统。 小人国的交通部将提供一些交通信息给你，你的任务是根据当前的交通情况回答查询的问题。交通信息可以分为以下几种格式：

• Close r1 c1 r2 c2：相邻的两座城市(r1, c1)和(r2, c2)之间的道路被堵塞了；
• Open r1 c1 r2 c2：相邻的两座城市(r1, c1)和(r2, c2)之间的道路被疏通了；
• Ask r1 c1 r2 c2：询问城市(r1, c1)和(r2, c2)是否连通。如果存在一条路径使得这两条城市连通，则返回Y，否则返回N。

注：ri表示行数，ci表示列数，1 \leq r_i \leq 2, 1 \leq c_i \leq C。

输入输出格式

输入格式：
第一行只有一个整数C，表示网格的列数。接下来若干行，每行为一条交通信息，以单独的一行Exit作为结束。我们假设在一开始所有的道路都是堵塞的。我们保证C小于等于100000，信息条数小于等于100000。

输出格式：
对于每个查询，输出一个Y或N。

输入输出样例

输入样例#1：

2
Open 1 1 1 2
Open 1 2 2 2
Ask 1 1 2 2
Ask 2 1 2 2
Exit

输出样例#1：

Y
N

说明

数据范围：
对于100%的数据，1 \leq C \leq 100000，1 \leq信息条数\leq 100000。

题解

设计可合并的状态

本题是一个线段树维护连通性的题目，那么必然要设计区间信息的合并，设计一个可合并的状态很有必要。这里我的设计是对于区间[l, r]存储(1, l)、(2, l)、(1, r)、(2, r)四个点两两间的连通性，总共有6种（即左上左下右上右下）。另外把横向道路放在线段树外面管理。
合并的时候，我们分情况讨论。例如需要维护左下右上这一情况，可以走的路线一共两种，如下图。

将六种情况都处理完毕合并就完成了。

修改

竖向道路：找到包含这条道路的长度为1的区间（即[x, x]），修改该区间内四种状态（左上右上、左下右下永远连通）即可。
横向道路：线段树递归的时候，发现有一个区间的mid和mid+1恰好是横向道路两端的c坐标时，在外部维护的横向道路修改后更新这个区间的信息，因为横向道路的影响是从这个区间开始产生的。

查询

直接查[c1, c2]？显然不行，因为有下面这种情况：

不一定直接能到，也许要往左往右绕，所以我们还得考虑绕的情况。除了[c1, c2]以外，还要把[1, c1]、[c2, C]两个区间的信息拿到，查c1上下两点，c2上下两点，再查这4个点之间的连通情况。

总结

线段树维护连通性，很新奇的用法。这道题的思维难度并不大，但是实现难度不小。主要细节集中于合并区间信息与查询答案的时候。写这个题的时候，用别人题解里的程序拍了好久才改出来。总之是很烦人的就对了。

代码

注：区间信息中，lurd是左(left)上(up)右(right)上(down)的意思，其他的以此类推。ru数组是上方(up)的横向道路(road)，rd以此类推。

// Code by KSkun, 2018/2
#include <cstdio>
#include <cstring>
#include <algorithm>

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
            : *p1++;
}

inline int readint() {
    register int res = 0, neg = 1;
    char c = fgc(); 
    while (c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while (c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005;

int c, r1, c1, r2, c2;
char op;

inline bool isop(char c) {
    return c == 'O' || c == 'C' || c == 'A' || c == 'E';
}

inline char readop() {
    char c = fgc();
    while (!isop(c)) c = fgc();
    return c;
}

#define lch o << 1
#define rch o << 1 | 1
#define mid ((l + r) >> 1)

bool ru[MAXN], rd[MAXN];

struct Data {
    int l, r;
    bool luru, ldrd, luld, rurd, lurd, ldru;
} tree[MAXN << 2];

inline void merge(Data *rt, Data ls, Data rs) { // 合并区间信息 
    rt->l = ls.l;
    rt->r = rs.r;
    rt->luru = (ls.luru && ru[ls.r] && rs.luru) || (ls.lurd && rd[ls.r] && rs.ldru); // 左上右上
    rt->lurd = (ls.luru && ru[ls.r] && rs.lurd) || (ls.lurd && rd[ls.r] && rs.ldrd); // 左上右下
    rt->ldru = (ls.ldru && ru[ls.r] && rs.luru) || (ls.ldrd && rd[ls.r] && rs.ldru); // 左下右上
    rt->ldrd = (ls.ldru && ru[ls.r] && rs.lurd) || (ls.ldrd && rd[ls.r] && rs.ldrd); // 左下右下
    rt->luld = ls.luld || (ls.luru && ru[ls.r] && rs.luld && rd[ls.r] && ls.ldrd); // 左上左下
    rt->rurd = rs.rurd || (rs.luru && ru[ls.r] && ls.rurd && rd[ls.r] && rs.ldrd); // 右上右下
} 

inline void build(int o, int l, int r) {
    if (l == r) {
        tree[o].l = tree[o].r = l;
        tree[o].luru = tree[o].ldrd = true;
        return;
    }
    build(lch, l, mid);
    build(rch, mid + 1, r);
    merge(&tree[o], tree[lch], tree[rch]);
}

inline void modify1(int o, int l, int r, int x, bool comm) {
    if (l == r) {
        tree[o].luld = tree[o].rurd = tree[o].lurd = tree[o].ldru = comm;
        return;
    }
    if (x <= mid) modify1(lch, l, mid, x, comm);
    if (x > mid) modify1(rch, mid + 1, r, x, comm);
    merge(&tree[o], tree[lch], tree[rch]);
}

inline void modify2(int o, int l, int r, int x, bool up, bool comm) {
    if (mid == x) {
        if(up) ru[x] = comm; else rd[x] = comm;
        merge(&tree[o], tree[lch], tree[rch]);
        return;
    }
    if (x <= mid) modify2(lch, l, mid, x, up, comm);
    if (x > mid) modify2(rch, mid + 1, r, x, up, comm);
    merge(&tree[o], tree[lch], tree[rch]);
}

inline Data query(int o, int l, int r, int ll, int rr) {
    if (l >= ll && r <= rr) {
        return tree[o];
    }
    if (rr <= mid) return query(lch, l, mid, ll, rr);
    else if (ll > mid) return query(rch, mid + 1, r, ll, rr);
    else {
        Data res;
        merge(&res, query(lch, l, mid, ll, mid), query(rch, mid + 1, r, mid + 1, rr));
        return res;
    }
}

int main() {
    c = readint();
    build(1, 1, c);
    for (;;) {
        op = readop();
        if (op == 'E') break;
        r1 = readint();
        c1 = readint();
        r2 = readint();
        c2 = readint();
        if (c1 > c2) {
            std::swap(r1, r2);
            std::swap(c1, c2);
        }
        if (op == 'O') {
            if (r1 == r2) {
                modify2(1, 1, c, c1, r1 == 1, true);
            } else {
                modify1(1, 1, c, c1, true);
            }
        }
        if (op == 'C') {
            if (r1 == r2) {
                modify2(1, 1, c, c1, r1 == 1, false);
            } else {
                modify1(1, 1, c, c1, false);
            }
        }
        if (op == 'A') {
            Data rm = query(1, 1, c, c1, c2), rl = query(1, 1, c, 1, c1), 
                rr = query(1, 1, c, c2, c);
            bool b1, b2, b3, b4;
            if (r1 == 1 && r2 == 1) {
                b1 = rm.luru;
                b2 = rl.rurd && rm.ldru;
                b3 = rr.luld && rm.lurd;
                b4 = rl.rurd && rm.ldrd && rr.luld;
                if(b1 || b2 || b3 || b4) printf("Y\n"); else printf("N\n");
            } else if (r1 == 1 && r2 == 2) {
                b1 = rm.lurd;
                b2 = rl.rurd && rm.ldrd;
                b3 = rr.luld && rm.luru;
                b4 = rl.rurd && rm.ldru && rr.luld;
                if(b1 || b2 || b3 || b4) printf("Y\n"); else printf("N\n");
            } else if (r1 == 2 && r2 == 1) {
                b1 = rm.ldru;
                b2 = rl.rurd && rm.luru;
                b3 = rr.luld && rm.ldrd;
                b4 = rl.rurd && rm.lurd && rr.luld;
                if(b1 || b2 || b3 || b4) printf("Y\n"); else printf("N\n");
            } else {
                b1 = rm.ldrd;
                b2 = rl.rurd && rm.lurd;
                b3 = rr.luld && rm.ldru;
                b4 = rl.rurd && rm.luru && rr.luld;
                if(b1 || b2 || b3 || b4) printf("Y\n"); else printf("N\n");
            }
        }
    }
    return 0;
}