bzoj 1018 堵塞的交通traffic
Description
有一天，由于某种穿越现象作用，你来到了传说中的小人国
小人国的布局非常奇特，整个国家的交通系统可以被看成是一个(2)行(C)列的矩形网格，网格上的每个点代表一个城市，相邻的城市之间有一条道路，所以总共有2(C)个城市和(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”作为结束。
我们假设在一开始所有的道路都是堵塞的。
我们保证 C小于等于(100000)，信息条数小于等于(100000)。
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
题解
只有两行，我们可以维护列区间([l, r])矩形的联通性
记录区间矩形
(左上,左下),(右上,右下),(左上,右上),(左下,右下),(左上,右下),(左下,右上)点对是否联通
合并两个相邻的区间时，矩形这些条件也很好维护
对于最底层的矩形也就是区间([l, l + 1])
我们单独记录每个小矩形内的四条边， 来维护区间([l, l + 1])
这样就可以维护整棵线段树了
问题是询问（假定(y_1 <= y_2)）
单独把包含询问的两个点的矩形拿出来并不能解决问题，
因为一个点（除了端点）都属于两个矩形，左边的点，可以借助其存在的坐矩形达到右边的点，右边的点同理
图是网图， 坐标反了， 凑合看吧
对于竖线((y_1 = y_2))，提取出来([1, y_1], [y_1, n + 1]) 来获得答案
对于其他，提取出([1, y_1],[y_1, y_2], [y_2, n + 1]) 来获得答案
具体怎么合并区间和获得答案看看代码自己画画图，也就懂了
struct BIT {
struct node {
//l, r, u, d, p, q
//(左上,左下),(右上,右下),(左上,右上),(左下,右下),(左上,右下),(左下,右上)点对是否联通
bool l, r, u, d, p, q;
} tr[N << 2];
bool edge[N][4]; //小矩形内部上下左右四条表是否存在
node unit(const node&a, const node& b) {
node c;
c.l = a.l | (a.u & a.d & b.l);
c.r = b.r | (b.u & b.d &a.r);
c.u = (a.u & b.u) | (a.p & b.q);
c.d = (a.d & b.d) | (a.q & b.p);
c.p = (a.u & b.p) | (a.p & b.d);
c.q = (a.d & b.q) | (a.q & b.u);
return c;
}
void check(int p, int id) {
tr[p].u = edge[id][0];
tr[p].d = edge[id][1];
tr[p].l = edge[id][2];
tr[p].r = edge[id][3];
tr[p].p = tr[p].q = 0;
tr[p].u |= tr[p].l & tr[p].r & tr[p].d;
tr[p].d |= tr[p].l & tr[p].r & tr[p].u;
tr[p].l |= tr[p].u & tr[p].r & tr[p].d;
tr[p].r |= tr[p].l & tr[p].u & tr[p].d;
tr[p].p = (tr[p].u & tr[p].r) | (tr[p].l & tr[p].d);
tr[p].q = (tr[p].d & tr[p].r) | (tr[p].l & tr[p].u);
}
//默认道路全部关闭，不需要build
//坐标(x1, y1)在(x2, y2)的左边(y1 <= y2)
void change(int p, int l, int r, int x1, int y1, int x2, int y2, bool open) {
if (l + 1 == r && y1 >= l && y2 <= r) {
if (y1 ^ y2)
if (x1 == 1)
edge[l][0] = open;
else
edge[l][1] = open;
else if (x1 ^ x2)
if (y1 == l)
edge[l][2] = open;
else
edge[l][3] = open;
check(p, l);
return;
}
int mid = l + r >> 1;
if (mid >= y2)
change(p << 1, l, mid, x1, y1, x2, y2, open);
if (mid <= y1)
change(p << 1 | 1, mid, r, x1, y1, x2, y2, open);
tr[p] = unit(tr[p << 1], tr[p << 1 | 1]);
}
//坐标(x1, y1)在(x2, y2)的左边(y1 <= y2)
node ask(int p, int l, int r, int y1, int y2) {
if (y1 == y2)
return node();
if (y1 <= l && r <= y2)
return tr[p];
int mid = l + r >> 1;
if (mid >= y2)
return ask(p << 1, l, mid, y1, y2);
if (mid <= y1)
return ask(p << 1 | 1, mid, r, y1, y2);
return unit(ask(p << 1, l, mid, y1, y2), ask(p << 1 | 1, mid, r, y1, y2));
}
bool aask(int n, int x1, int y1, int x2, int y2) {
if (y1 ^ y2) {
node a = ask(1, 1, n, 1, y1);
node b = ask(1, 1, n, y1, y2);
node c = ask(1, 1, n, y2, n);
if (x1 == x2)
if (x1 == 1)
return b.u | ((a.r | b.l) & b.d & (c.l | b.r));
else
return b.d | ((a.r | b.l) & b.u & (c.l | b.r));
else
if (x1 == 1)
return b.p | (a.r & b.d) | (c.l & b.u);
else
return b.q | (c.l & b.d) | (a.r & b.u);
} else {
if (x1 == x2)
return 1;
return ask(1, 1, n, 1, y1).r | ask(1, 1, n, y1, n).l;
}
return 0;
}
} bit;
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
++n;
string s;
for (cin >> s; s[0] ^ 'E'; cin >> s) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
if (y1 > y2)
swap(x1, x2), swap(y1, y2);
if (s[0] == 'O')
bit.change(1, 1, n, x1, y1, x2, y2, 1);
else if (s[0] == 'C')
bit.change(1, 1, n, x1, y1, x2, y2, 0);
else
cout << (bit.aask(n, x1, y1, x2, y2) ? 'Y' : 'N') << '
';
}
return 0;
}