Description

有一天, 由于某种穿越现象作用, 你来到了传说中的小人国. 小人国的布局非常奇特, 整个 国家的交通系统可以被看成是一个 \(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;

Input

第一行只有一个整数 \(C\), 表示网格的列数. 接下来若干行, 每行为一条交通信息, 以单独的一行 Exit 作为结束. 我们假设在一开始所有的道路都是堵塞的.

Output

对于每个查询, 输出一个 Y 或 N.

Sample Input

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

Sample Output

Y
N

Data Range

我们保证 \(C\) 小于等于 \(100000\), 信息条数小于等于 \(100000\).

Explanation

当然就是一发线段树了...... 维护一段区间内从左上、左下、右上、右下互相到达的连通性, 然后必须要存 6 种情况, 而不仅仅是 4 种 (不然有些情况考虑不到).

一开始写了一个标记了 4 种状态的线段树, 交上去 WA, 然后不明觉厉找了一个题解一看 发现有 6 种状态然后赶紧改掉...... 结果调了半天还是过不去......

索性重写一遍, 但是写完还是 pyjudge 过不了, 一看发现我和标解代码建树方式不一样, 直接把自底向上建树改成自顶向下建树, 而且区间一定是 \(n\) 而不是 \(2^{\lfloor \log n \rfloor}\), 但是这样还属 pyjudge 不过......

然后又调了好久发现一个问题: 本来应该是 change(lc(p), x1, y1, x2, y2, val); 的递归我给写成了 change(lc(p), x1, x2, y1, y2, val);. ...... QAQ

就这一点小问题调了我七个小时...... QAQ

顺便附带一下原来的 WA 代码:


#include <iostream>
#include <cstdlib>
#include <cstdio>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
#define range(_begin,_end) rep(_,_begin,_end)
using namespace std;
typedef long long lli;
const int maxn = 300100;

class FiddledSegmentTree
{
public:
    int n, lbnd[maxn], rbnd[maxn],
        vacc[maxn][7]; // Accessible: 1 TL-TR, 2 TL-BR, 3 BL-TR, 4 BL-BR, 5 TL-BL, 6 TR-BR
    int hor_acc[maxn][3]; // Top, bottom
    #define lc(__x) (2*(__x))
    #define rc(__x) (2*(__x)+1)
    void build_tree(int n_)
    {
        n = 1; while (n < n_) n *= 2;
        for (int i = 1; i <= n; i++) {
            lbnd[n + i - 1] = rbnd[n + i - 1] = i;
            vacc[n + i - 1][1] = vacc[n + i - 1][4] = true;
            vacc[n + i - 1][2] = vacc[n + i - 1][3] = false;
            vacc[n + i - 1][5] = vacc[n + i - 1][6] = false;
        }
        for (int i = n - 1; i >= 1; i--) {
            lbnd[i] = lbnd[2 * i];
            rbnd[i] = rbnd[2 * i + 1];
            range(1,6) vacc[i][_] = false;
        }
        return ;
    }
    void update_vacc(int p)
    {
        #define work_change(__x,__y,__z) (vacc[lc(p)][__x] &&\
            hor_acc[rbnd[lc(p)]][__y] && vacc[rc(p)][__z])
        vacc[p][1] = work_change(1, 1, 1) || work_change(2, 2, 3);
        vacc[p][2] = work_change(1, 1, 2) || work_change(2, 2, 4);
        vacc[p][3] = work_change(3, 1, 1) || work_change(4, 2, 3);
        vacc[p][4] = work_change(3, 1, 2) || work_change(4, 2, 4);
        #define work_vchange(__x,__y,__z) (vacc[__y][__x] || (vacc[__y][1]\
            && hor_acc[rbnd[lc(p)]][1] && vacc[__z][5] && hor_acc[rbnd[lc(p)]][2]\
            && vacc[__y][4]))
        // vacc[p][5] = vacc[lc(p)][5] ||
        //     (vacc[lc(p)][1] && hor_acc[rbnd[lc(p)]][1] && vacc[rc(p)][5] &&
        //     hor_acc[rbnd[lc(p)]][2] && vacc[lc(p)][4]);
        // vacc[p][6] = vacc[rc(p)][6] ||
        //     (vacc[rc(p)][1] && hor_acc[rbnd[lc(p)]][1] && vacc[lc(p)][6] &&
        //     hor_acc[rbnd[lc(p)]][2] && vacc[rc(p)][4]);
        vacc[p][5] = work_vchange(5, lc(p), rc(p));
        vacc[p][6] = work_vchange(6, rc(p), lc(p));
        return ;
    }
    void change_vert(int pos, bool v)
    {
        int p = n + pos - 1;
        vacc[p][1] = vacc[p][4] = true;
        vacc[p][2] = vacc[p][3] = v;
        vacc[p][5] = vacc[p][6] = v;
        for (p /= 2; p >= 1; p /= 2)
            update_vacc(p);
        return ;
    }
    void change_horz(int pos, int vert, bool v)
    {
        int p = n + pos - 1,
            q = n + (pos+1) - 1;
        hor_acc[pos][vert] = v;
        for (p /= 2, q /= 2; p >= 1 && q >= 1; p /= 2, q /= 2) {
            update_vacc(p);
            if (q != p) update_vacc(q);
        }
        return ;
    }
    bool query__(int p, int l, int r, int mode)
    {
        if (l < 0 || l > n || r < 0 || r > n || l > r)
            return false;
        if (l == lbnd[p] && r == rbnd[p])
            return vacc[p][mode];
        if (r <= rbnd[lc(p)]) return query__(lc(p), l, r, mode);
        else if (l >= lbnd[rc(p)]) return query__(rc(p), l, r, mode);
        // That would be an excessive amount of querying...
        #define work_query(__x,__y,__z) (query__(lc(p),l,rbnd[lc(p)],__x) &&\
            hor_acc[rbnd[lc(p)]][__y] && query__(rc(p),lbnd[rc(p)],r,__z))
        // Yes. We used macros. That's a lot nicer, isn't it?
        if (mode == 1) return work_query(1, 1, 1) || work_query(2, 2, 3);
        if (mode == 2) return work_query(1, 1, 2) || work_query(2, 2, 4);
        if (mode == 3) return work_query(3, 1, 1) || work_query(4, 2, 3);
        if (mode == 4) return work_query(3, 1, 2) || work_query(4, 2, 4);
        // Another strange aspect of things
        if (mode == 5) return query__(lc(p), l, rbnd[lc(p)], 5) || (
            query__(lc(p), l, rbnd[lc(p)], 1) && hor_acc[rbnd[lc(p)]][1] &&
            query__(rc(p), lbnd[rc(p)], r, 5) && hor_acc[rbnd[lc(p)]][2] &&
            query__(lc(p), l, rbnd[lc(p)], 4));
        if (mode == 6) return query__(rc(p), lbnd[rc(p)], r, 6) || (
            query__(rc(p), lbnd[rc(p)], r, 1) && hor_acc[rbnd[lc(p)]][1] &&
            query__(lc(p), l, rbnd[lc(p)], 6) && hor_acc[rbnd[lc(p)]][2] &&
            query__(rc(p), lbnd[rc(p)], r, 4));
        return false;
    }
    void change(int x1, int y1, int x2, int y2, bool val)
    {
        // Keep arrangement.
        if (x1 > x2) swap(x1, x2), swap(y1, y2);
        // Change vertical data
        if (x1 == x2) change_vert(x1, val);
        // Change horizontal data
        else change_horz(x1, y1, val);
        return ;
    }
    bool query(int x1, int y1, int x2, int y2)
    {
        // Keep arrangement.
        if (x1 > x2) swap(x1, x2), swap(y1, y2);
        // Same row and same column.
        if (x1 == x2 && y1 == y2) return true;
        // On the same column.
        // if (x1 == x2) return query__(1, x1, x2, 2);
        // On the same row (ensured different columns)
        if (y1 == 1 && y2 == 1) return query__(1, x1, x2, 1) || (
            query__(1, 1, x1, 5) && query__(1, x1, x2, 4) && query__(1, x2, n, 6));
        if (y1 == 2 && y2 == 2) return query__(1, x1, x2, 4) || (
            query__(1, 1, x1, 5) && query__(1, x1, x2, 1) && query__(1, x2, n, 6));
        // On different rows (different columns)
        if (y1 == 1 && y2 == 2) return query__(1, x1, x2, 2) || (
            query__(1, 1, x1, 5) && query__(1, x1, x2, 4)) || (
            query__(1, x1, x2, 1) && query__(1, x2, n, 6));
        if (y1 == 2 && y2 == 1) return query__(1, x1, x2, 3) || (
            query__(1, 1, x1, 5) && query__(1, x1, x2, 1)) || (
            query__(1, x1, x2, 4) && query__(1, x2, n, 6));
        //
        // int mode = 0;
        // #define check_query(__x,__y,__z) if(y1==(__x)&&y2==(__y)) mode=(__z)
        // check_query(1, 1, 1);
        // check_query(1, 2, 2);
        // check_query(2, 1, 3);
        // check_query(2, 2, 4);
        // // Returning data.
        // // printf("querying %d %d %d\n", x1, x2, mode);
        // bool res = query__(1, x1, x2, mode);
        // return res;
        return false;
    }
} st;

int C;
char str[20];

int main(int argc, char** argv)
{
    scanf("%d", &C);
    st.build_tree(C);
    while (true) {
        scanf("%s", str);
        int r1, c1, r2, c2;
        if (str[0] == 'O') {
            scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
            st.change(c1, r1, c2, r2, true);
        } else if (str[0] == 'C') {
            scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
            st.change(c1, r1, c2, r2, false);
        } else if (str[0] == 'A') {
            scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
            bool res = st.query(c1, r1, c2, r2);
            printf("%s\n", res ? "Y" : "N");
        } else {
            break;
        }
    }
    return 0;
}

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

#define rep(_var,_begin,_end) for (int _var=_begin;_var<=_end;_var++)
#define range(_begin,_end) rep(_,_begin,_end)
using namespace std;
typedef long long lli;
const int maxn = 300100;

class SegmentTree
{
public:
    struct status {
        bool norm[2][2]; // TL->TR, TL->BR, BL->TR, BL->BR
        bool rev[2]; // TL->BL, TR->BR
    };
    int n, lbnd[maxn], rbnd[maxn], mid[maxn];
    bool hor_acc[maxn][2];
    status state[maxn];
    #define lc(__x) ((__x)*2)
    #define rc(__x) ((__x)*2+1)
    status join(status s1, status s2, bool b[])
    {
        status res;
        rep(i, 0, 1) rep(j, 0, 1)
            res.norm[i][j] = (s1.norm[i][0] && b[0] && s2.norm[0][j])
                || (s1.norm[i][1] && b[1] && s2.norm[1][j]);
        res.rev[0] = s1.rev[0] || (s1.norm[0][0] && b[0] && s2.rev[0]
            && b[1] && s1.norm[1][1]);
        res.rev[1] = s2.rev[1] || (s2.norm[0][0] && b[0] && s1.rev[1]
            && b[1] && s2.norm[1][1]);
        return res;
    }
    void build(int p, int l, int r)
    {
        lbnd[p] = l, rbnd[p] = r;
        mid[p] = (lbnd[p] + rbnd[p]) / 2;
        if (l == r) { range(0,1)
            state[p].norm[_][_] = true;
        } else {
            build(lc(p), l, mid[p]);
            build(rc(p), mid[p] + 1, r);
        }
        return ;
    }
    void build_tree(int n_)
    {
        n = n_;
        build(1, 1, n);
        return ;
    }
    status query_range(int p, int l, int r)
    {
        if (l <= lbnd[p] && r >= rbnd[p])
            return state[p];
        if (r <= mid[p])
            return query_range(lc(p), l, r);
        else if (l > mid[p])
            return query_range(rc(p), l, r);
        return join(query_range(lc(p), l, r),
            query_range(rc(p), l, r),
            hor_acc[p]);
    }
    void change(int p, int x1, int y1, int x2, int y2, int val)
    {
        if (x1 == x2 && y1 == mid[p]) {
            hor_acc[p][x1] = val;
            state[p] = join(state[lc(p)], state[rc(p)], hor_acc[p]);
        } else if (lbnd[p] == rbnd[p]) {
            status& st = state[p];
            range(0,1) st.norm[_][!_] = st.rev[_] = val;
        } else {
            if (y2 <= mid[p])
                // change(lc(p), x1, x2, y1, y2, val);
                change(lc(p), x1, y1, x2, y2, val);
            else
                // change(rc(p), x1, x2, y1, y2, val);
                change(rc(p), x1, y1, x2, y2, val);
            state[p] = join(state[lc(p)], state[rc(p)], hor_acc[p]);
        }
        return ;
    }
    void change(int x1, int y1, int x2, int y2, bool val)
    {
        if (y1 > y2) {
            swap(x1, x2);
            swap(y1, y2);
        } x1--; x2--;
        change(1, x1, y1, x2, y2, val);
        return ;
    }
    bool query(int x1, int y1, int x2, int y2)
    {
        if (y1 > y2) {
            swap(x1, x2);
            swap(y1, y2);
        } x1--; x2--;
        status lst = query_range(1, 1, y1), // Left boundary to interval left
            rst = query_range(1, y2, n), // Interval right to right boundary
            mst = query_range(1, y1, y2); // Between the Interval
        bool res = false;
        rep(i, 0, 1) rep(j, 0, 1)
            if (mst.norm[i][j] && (i == x1 || lst.rev[1]) && (j == x2 || rst.rev[0]))
                res = true;
        return res;
    }
} st;

int n;
char str[20];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    st.build_tree(n);
    while (true) {
        scanf("%s", str);
        int r1, c1, r2, c2;
        if (str[0] == 'O') {
            scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
            st.change(r1, c1, r2, c2, true);
        } else if (str[0] == 'C') {
            scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
            st.change(r1, c1, r2, c2, false);
        } else if (str[0] == 'A') {
            scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
            bool res = st.query(r1, c1, r2, c2);
            printf("%s\n", res ? "Y" : "N");
        } else {
            break;
        }
    }
    return 0;
}