题解 P4246 【[SHOI2008]堵塞的交通】
scallop
2018-03-14 21:29:54
这道题真是一道非常**好**的的题目。
我们考虑使用线段树维护连通性。分别维护一个区间中
$$[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$ 表示同一列的另一行。那么我们只需要分情况判断是否可以到达就行了。
```cpp
#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;
}
```