BZOJ 1018 - [SHOI2008]堵塞的交通traffic

#图论 #数据结构 #线段树 #好题

Published on 2016-08-25

描述

有一天，由于某种穿越现象作用，你来到了传说中的小人国。小人国的布局非常奇特，整个国家的交通系统可以被看成是一个 $2$ 行 $C(C\le 100000)$ 列的矩形网格，网格上的每个点代表一个城市，相邻的城市之间有一条道路，所以总共有 $2C$ 个城市和 $3C-2$ 条道路。小人国的交通状况非常槽糕。有的时候由于交通堵塞，两座城市之间的道路会变得不连通，直到拥堵解决，道路才会恢复畅通。初来咋到的你决心毛遂自荐到交通部某份差事，部长听说你来自一个科技高度发达的世界，喜出望外地要求你编写一个查询应答系统，以挽救已经病入膏肓的小人国交通系统。

小人国的交通部将提供一些交通信息（不多于 $100000$ 个）给你，你的任务是根据当前的交通情况回答查询的问题。交通信息可以分为以下几种格式：

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。

分析

我们看看两个点之间的路径可以是怎样的，有两种情况：

情况一：路径在两个点所在列中间。

情况二：路径超出两个点所在列的范围。

我们先看第一种情况怎么维护，这图不是树形的结构，而且存在加边删边两种情况，似乎不好维护？但仔细观察发现，这个图的边比较单一，只可能跟相邻的点有边，这很像链式结构，我们能否使用常用维护链式结构的工具线段树来维护呢？
答案是完全可以！

我们对线段树的每条线段 $[l, r)$ ，维护 $l$ 与 $r - 1$ 这两个点的联通性，不妨设第一行的点为 0，第二行的点为 1，则使用 $G[i][j]$ 来表示 $l$ 这边的 $i$ 能否与 $r - 1$ 这边的 $j$ 联通。
定义节点信息很容易，关键是怎么处理合并呢？比如我们要将 $[l, \textrm{mid})$ 与 $[\textrm{mid}, r)$ 合并成 $[l, r)$ ，怎么做？

如果 $i, j$ 联通，那么 $\textrm{mid}-1\rightarrow \textrm{mid}$ 这两列必然存在一条边（相邻两列之间的边要在线段树外单独记录），那么我们就枚举是在上面还是在下面，转移即可。注意除了 $\textrm{mid}-1\rightarrow \textrm{mid}$ 的边是直的，其余的边都不一定是直的，可能是绕来绕去才到达的，这里画成直线只是表示联通关系。
查询也很容易，将待查询区间在线段树上分解，然后依次合并即可。显然每次合并，都能合并成一个完整的区间。

如果由第二种情况怎么办呢？我们发现无论怎么绕，在合法路径上，对于左边的点，都有一个最左边的点，最右边的点，都有一个最左边的点。那么我们通过二分，找到最左边的点可以到达的最左的列，然后走到那一列上去。接着找到最右边的点可以到达的最右的列，然后走到那一列上去，然后再次查询，如果存在路径，这条路径必定存在于在这两列中间，待查询的两个点也就能通过某种方式联通。这样做的正确性是显然的，即使不是第二种情况，也可以往左往右走，不会产生影响，无非就是原路返回提前的那一段。

单次修改的复杂度为 $O(\log n)$ ，查询的复杂度为 $O(\log^2n)$ ，总复杂度为： $O(n\log^2n)$ ，十分不优。
刚刚的算法瓶颈在于要二分出最左边，最右边的列，我们也可以采取在线段树上爬行的方式（有点类似权值线段树找第 $k$ 大）来达到同样的效果，查询的复杂度降为单次 $O(\log n)$ ，这样总复杂度降为 $O(n\log n)$ 。~~可是我懒得写~~

总结：本题的的意图是维护联通性，必须要观察出这个图实际上还是链式结构，可以使用维护链式结构的工具线段树来维护。
拿到一个题目，我们一定要观察出它的特性，再去想这个特性往往用什么办法去处理，这样才能够有针对性的解题，而至于陷入“一不会做就看题解，一看题解马上就会做”的窘境。

代码

//  Created by Sengxian on 08/22/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 1018 线段树维护连通性
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 100000 + 3;
bool have_edge[maxn][2];
int n;
namespace segment_tree {
    #define ls (((o) << 1) + 1)
    #define rs (((o) << 1) + 2)
    #define mid (((l) + (r)) >> 1)
    const int max_node = (1 << 17) * 2 + 3;
    struct node {
        int l, r;
        bool G[2][2];
        node(): l(-1), r(-1) {}
    }datas[max_node];
    inline node merge(const node &lhs, const node &rhs) {
        if (lhs.l == -1) return rhs;
        else if (rhs.l == -1) return lhs;
        node ne;
        ne.l = lhs.l, ne.r = rhs.r;
        for (int i = 0; i < 2; ++i)
            for (int j = 0; j < 2; ++j)
                ne.G[i][j] = (lhs.G[i][0] && have_edge[lhs.r - 1][0] && rhs.G[0][j]) ||
                             (lhs.G[i][1] && have_edge[lhs.r - 1][1] && rhs.G[1][j]);
        return ne;
    }
    inline void build(int o, int l, int r) {
        datas[o].l = l, datas[o].r = r;
        memset(datas[o].G, 0, sizeof datas[o].G);
        if (r - l == 1) datas[o].G[0][0] = datas[o].G[1][1] = 1;
        else build(ls, l, mid), build(rs, mid, r);
    }
    inline node query(int o, int l, int r, int a, int b) {
        if (l >= a && r <= b) return datas[o];
        else {
            node ret;
            if (mid > a) ret = query(ls, l, mid, a, b);
            if (mid < b) ret = merge(ret, query(rs, mid, r, a, b));
            return ret;
        }
    }
    inline void modify(int o, int l, int r, int pos, int sign) {
        if (r - l == 1) {
            if (~sign) datas[o].G[0][1] = datas[o].G[1][0] = sign;
        } else {
            if (pos < mid) modify(ls, l, mid, pos, sign);
            else modify(rs, mid, r, pos, sign);
            datas[o] = merge(datas[ls], datas[rs]);
        }
    }
    #define x first
    #define y second
    typedef pair<int, int> point;
    inline point go_left(const point &p) {
        int l = -1, r = p.x;
        while (r - l > 1) {
            node now = query(0, 0, n, mid, p.x + 1);
            if (now.G[0][p.y] || now.G[1][p.y]) r = mid;
            else l = mid;
        }
        if (r == p.x) return p;
        else {
            node now = query(0, 0, n, r, p.x + 1);
            return now.G[0][p.y] ? point(r, 0) : point(r, 1);
        }
    }
    inline point go_right(const point &p) {
        int l = p.x, r = n;
        while (r - l > 1) {
            node now = query(0, 0, n, p.x, mid + 1);
            if (now.G[p.y][0] || now.G[p.y][1]) l = mid;
            else r = mid;
        }
        if (l == p.x) return p;
        else {
            node now = query(0, 0, n, p.x, l + 1);
            return now.G[p.y][0] ? point(l, 0) : point(l, 1);
        }
    }
    # undef x
    # undef y
}

using namespace segment_tree;

void print(const node &o) {
    printf("0->0:%d 0->1:%d\n1->0:%d 1->1:%d\n", o.G[0][0], o.G[0][1], o.G[1][0], o.G[1][1]);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    n = ReadInt();
    segment_tree::build(0, 0, n);
    memset(have_edge, 0, sizeof (bool) * 2 * n);
    while (true) {
        static char str[10];
        static int x1, y1, x2, y2;
        scanf("%s", str);
        if (str[0] == 'E') break;
        y1 = ReadInt() - 1, x1 = ReadInt() - 1, y2 = ReadInt() - 1, x2 = ReadInt() - 1;
        if (!(x1 < x2 || (x1 == x2 && y1 < y2))) swap(x1, x2), swap(y1, y2);
        if (str[0] == 'O' || str[0] == 'C') {
            int sign = str[0] == 'O';
            if (x1 == x2) {
                if (y1 != y2) modify(0, 0, n, x1, sign);
            } else {
                have_edge[x1][y1] = sign;
                modify(0, 0, n, x1, -1);
            }
        } else if (str[0] == 'A') {
            point p1 = go_left(point(x1, y1));
            point p2 = go_right(point(x2, y2));
            node ret = query(0, 0, n, p1.first, p2.first + 1);
            puts(ret.G[p1.second][p2.second] ? "Y" : "N");
        }
    }
    return 0;
}

BZOJ 1019 - [SHOI2008]汉诺塔 BZOJ 1016 - [JSOI2008]最小生成树计数

Sengxian's Blog

BZOJ 1018 - [SHOI2008]堵塞的交通traffic

描述

分析

代码