题解 P4246 【[SHOI2008]堵塞的交通】

这道题真是一道非常的的题目。

我们考虑使用线段树维护连通性。分别维护一个区间中

$$[l_1,r_1],[l_1,l_2],[l_1,r_2],[l_2,r_1],[l_2,r_2],[r_1,r_2]$$

这些点的连通性。 我们可以通过一定的讨论来得到 $O(1)$ 的方法通过子树更新信息(有些复杂,见代码)

然后我们可以完成单点修改了。

考虑询问操作。我们发现从点 $x_c$ 走到 $y_c$ 可能有四种情况:

$$1:x_c\to y_c$$$$2:x_c\to x_{!c}\to y_c$$$$3:x_c\to y_{!c}\to y_c$$$$4:x_c\to x_{!c}\to y_{!c}\to y_c$$

其中我们令 $!c$ 表示同一列的另一行。那么我们只需要分情况判断是否可以到达就行了。

#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <string>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;

struct segment
{
    int l;
    int r;
    int sum[2];
    bool e[3][2];
};

struct return_val
{
    bool e[3][2];
    bool operator = (const return_val &x)
    {
        for (int i = 0; i < 3; ++i)
        {
            for (int j = 0; j < 2; ++j)
                e[i][j] = x.e[i][j];
        }
    }
};

const int MAXN = 2e5 + 100;
int n, cnt;
bool a[MAXN][2];
segment tree[MAXN];

void pushup(int p)
{
    if (tree[p].l == tree[p].r)
        return;
    int l = p * 2, r = p * 2 + 1, mid = (tree[p].l + tree[p].r) / 2;
    memset(tree[p].e, 0, sizeof tree[p].e);
    tree[p].e[0][0] = (tree[l].e[0][0] && tree[r].e[0][0] && a[mid][0]) || (tree[l].e[0][1] && tree[r].e[1][0] && a[mid][1]);
    tree[p].e[0][1] = (tree[l].e[0][0] && tree[r].e[0][1] && a[mid][0]) || (tree[l].e[0][1] && tree[r].e[1][1] && a[mid][1]);
    tree[p].e[1][0] = (tree[l].e[1][0] && tree[r].e[0][0] && a[mid][0]) || (tree[l].e[1][1] && tree[r].e[1][0] && a[mid][1]);
    tree[p].e[1][1] = (tree[l].e[1][0] && tree[r].e[0][1] && a[mid][0]) || (tree[l].e[1][1] && tree[r].e[1][1] && a[mid][1]);
    tree[p].e[2][0] = tree[l].e[2][0] || (tree[p].e[0][1] && tree[p].e[1][1]) || (tree[p].e[0][0] && tree[p].e[1][0]) || (tree[p].e[0][0] && tree[p].e[1][1] && tree[r].e[2][1]) || (tree[l].e[0][0] && tree[l].e[1][1] && tree[r].e[2][0] && a[mid][0] && a[mid][1]);
    tree[p].e[2][1] = tree[r].e[2][1] || (tree[p].e[0][0] && tree[p].e[0][1]) || (tree[p].e[1][0] && tree[p].e[1][1]) || (tree[p].e[0][0] && tree[p].e[1][1] && tree[l].e[2][0]) || (tree[r].e[0][0] && tree[r].e[1][1] && tree[l].e[2][1] && a[mid][0] && a[mid][1]);
}

void add_row(int p, int x)
{
    if (tree[p].l == tree[p].r && tree[p].l == x)
        tree[p].e[0][0] = tree[p].e[0][1] = tree[p].e[1][0] = tree[p].e[1][1] = tree[p].e[2][0] = tree[p].e[2][1] = true;
    else if (tree[p].l <= x && tree[p].r >= x)
    {
        int mid = (tree[p].l + tree[p].r) / 2;
        if (x > mid)
            add_row(p * 2 + 1, x);
        else
            add_row(p * 2, x);
        pushup(p);
    }
}

void sub_row(int p, int x)
{
    if (tree[p].l == tree[p].r && tree[p].l == x)
    {
        tree[p].e[0][0] = tree[p].e[1][1] = true;
        tree[p].e[1][0] = tree[p].e[0][1] = false;
        tree[p].e[2][0] = tree[p].e[2][1] = false;
    }
    else if (tree[p].l <= x && tree[p].r >= x)
    {
        int mid = (tree[p].l + tree[p].r) / 2;
        if (x > mid)
            sub_row(p * 2 + 1, x);
        else
            sub_row(p * 2, x);
        pushup(p);
    }
}

void add_column(int p, int x, int c)
{
    if (tree[p].l == tree[p].r && tree[p].l == x)
        a[x][c] = true, tree[p].sum[c] = 1;
    else if (tree[p].l <= x && tree[p].r >= x)
    {
        int mid = (tree[p].l + tree[p].r) / 2;
        if (x > mid)
            add_column(p * 2 + 1, x, c);
        else
            add_column(p * 2, x, c);
        pushup(p);
    }
}

void sub_column(int p, int x, int c)
{
    if (tree[p].l == tree[p].r && tree[p].l == x)
        a[x][c] = false, tree[p].sum[c] = 0;
    else if (tree[p].l <= x && tree[p].r >= x)
    {
        int mid = (tree[p].l + tree[p].r) / 2;
        if (x > mid)
            sub_column(p * 2 + 1, x, c);
        else
            sub_column(p * 2, x, c);
        pushup(p);
    }
}

void open(int l1, int r1, int l2, int r2)
{
    if (l1 == l2)
        add_row(1, l1);
    else
    {
        if (l1 > l2)
            swap(l1, l2);
        if (!a[l1][r1])
        {
            add_column(1, l1, r1);
        }
    }
}

void close(int l1, int r1, int l2, int r2)
{
    if (l1 == l2)
        sub_row(1, l1);
    else
    {
        if (l1 > l2)
            swap(l1, l2);
        if (a[l1][r1])
            sub_column(1, l1, r1);
    }

}

return_val query_direct(int p, int l, int r)
{
    if (tree[p].l == l && tree[p].r == r)
        return (return_val){{tree[p].e[0][0], tree[p].e[0][1], tree[p].e[1][0], tree[p].e[1][1], tree[p].e[2][0], tree[p].e[2][1]}};
    else
    {
        return_val t1, t2;
        int mid = (tree[p].l + tree[p].r) / 2;
        if (r > mid)
            t2 = query_direct(p * 2 + 1, max(mid + 1, l), r);
        if (l <= mid)
            t1 = query_direct(p * 2, l, min(mid, r));
        if (l > mid)
            return t2;
        else if (r <= mid)
            return t1;
        else
        {
            return_val ret;
            ret.e[0][0] = (t1.e[0][0] && t2.e[0][0] && a[mid][0]) || (t1.e[0][1] && t2.e[1][0] && a[mid][1]);
            ret.e[0][1] = (t1.e[0][0] && t2.e[0][1] && a[mid][0]) || (t1.e[0][1] && t2.e[1][1] && a[mid][1]);
            ret.e[1][0] = (t1.e[1][0] && t2.e[0][0] && a[mid][0]) || (t1.e[1][1] && t2.e[1][0] && a[mid][1]);
            ret.e[1][1] = (t1.e[1][0] && t2.e[0][1] && a[mid][0]) || (t1.e[1][1] && t2.e[1][1] && a[mid][1]);
            ret.e[2][0] = t1.e[2][0] || (ret.e[0][1] && ret.e[1][1]) || (ret.e[0][0] && ret.e[1][0]) || (ret.e[0][0] && ret.e[1][1] && t2.e[2][1]) || (t1.e[0][0] && t1.e[1][1] && t2.e[2][0] && a[mid][0] && a[mid][1]);
            ret.e[2][1] = t2.e[2][1] || (ret.e[0][0] && ret.e[0][1]) || (ret.e[1][0] && ret.e[1][1]) || (ret.e[0][0] && ret.e[1][1] && t1.e[2][0]) || (t2.e[0][0] && t2.e[1][1] && t1.e[2][1] && a[mid][0] && a[mid][1]);
            return ret;
        }

    }
}

int query_left(int l, int r, int c)
{
    while (l < r)
    {
        int mid = (l + r) / 2;
        return_val j = query_direct(1, mid, r);
        if (j.e[c][c])
            r = mid;
        else
            l = mid + 1;
    }
    return r;
}

int query_right(int l, int r, int c)
{
    while (l < r)
    {
        int mid = (l + r + 1) / 2;
        return_val j = query_direct(1, l, mid);
        if (j.e[c][c])
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}

bool query(int l1, int r1, int l2, int r2)
{
    if (l1 > l2)
    {
        swap(l1, l2);
        swap(r1, r2);
    }
    return_val t = query_direct(1, l1, l2);
    if (t.e[r1][r2])
        return true;
    return_val t1 = query_direct(1, 1, l1), t2 = query_direct(1, l2, n);
    bool ld = t1.e[2][1], rd = t2.e[2][0];
    if (ld && t.e[r1 ^ 1][r2])
        return true;
    if (rd && t.e[r1][r2 ^ 1])
        return true;
    if (ld && rd && t.e[r1 ^ 1][r2 ^ 1])
        return true;
    return false;
}

void build(int p, int l, int r)
{
    tree[p].l = l;
    tree[p].r = r;
    if (tree[p].l != tree[p].r)
    {
        int mid = (l + r) / 2;
        build(p * 2, l, mid);
        build(p * 2 + 1, mid + 1, r);
    }
    else
        tree[p].e[0][0] = tree[p].e[1][1] = true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    build(1, 1, n);
    while (true)
    {
        string s;
        cin >> s;
        if (s[0] == 'E')
            break;
        int l1, c1, l2, c2;
        cin >> c1 >> l1 >> c2 >> l2;
        --c1;
        --c2;
        if (s[0] == 'O')
            open(l1, c1, l2, c2);
        if (s[0] == 'C')
            close(l1, c1, l2, c2);
        if (s[0] == 'A')
        {
            if (query(l1, c1, l2, c2))
                printf("Y\n");
            else
                printf("N\n");
        }
    }
    return 0;
}

发表于 2018-03-14 21:29:54 in 题解