2行c列的网格图, 一开始所有边都不存在. 支持两类操作: - 修改一条边的存在性 - 查询两个格点的连通性
(c, 操作数 ≤ 10^5) 感觉可以上线段树? 维护区间四个端点的连通性, 这是容易合并的. 但题目询问的是任意两点的连通性, 而不是保留[L,R]中的边, (r1,L), (r2,R) 的连通性.
**** L --------~~~~~
* | ~
*****------- R ~~~~学习一下题解. 发现这根本不是问题......
***不在(L,R)内, 但是在[1,L]中啊; ~~~不在(L,R)内, 但是在[R,c]中啊......
一开始看的是Po姐的题解, 在线段树上二分查找, 找到***的最左端L'和~~~的最右端R', 然后查询[L',R']的信息.
我觉得这个想法不错. Po姐的代码有点长诶......不虚, 码码码......
完成了下面那份4.6KB的代码, 然后在 rank list 中发现大多数代码都是3KB左右的......
事实上, 我们可以直接在[1,L]中查找(1,L)和(2,L)的连通性......这个信息也是易于合并的......QAQ
嗯, Po姐的代码5.3KB......
启发: 区间外的信息在另一个区间内.
#define ALL 1, 0, n-1
#define LEFT o*2, l, m
#define RIGHT o*2+1, m+1, r
typedef pair<int, int> P;
const int N = 1e5;
struct Info {
bool x[2][2];
Info(bool y=false)
{
x[0][0] = x[1][1] = true;
x[0][1] = x[1][0] = y;
}
friend Info merge(const Info& a, const Info& b, bool u, bool v)
{
Info c;
rep (i, 0, 2) rep (j, 0, 2)
c.x[i][j] = (a.x[i][0] & u & b.x[0][j]) | (a.x[i][1] & v & b.x[1][j]);
return c;
}
};
bool f[N][2];
int n;
struct Seg {
bool first;
Info v[N*4];
void up(int o, int i)
{
v[o] = merge(v[o*2], v[o*2+1], f[i][0], f[i][1]);
}
void build(int o, int l, int r)
{
if (l == r) return;
int m = (l+r)/2;
build(LEFT);
build(RIGHT);
up(o, m);
}
int go_left(int y, Info& i, int o, int l, int r)
{
if (l == r) {
Info j = first ? v[o] : merge(v[o], i, f[r][0], f[r][1]);
first = false;
if (j.x[0][y] || j.x[1][y]) return i = j, -1;
return l;
}
int m = (l+r)/2;
Info j = first ? v[o*2+1] : merge(v[o*2+1], i, f[r][0], f[r][1]);
if (j.x[0][y] || j.x[1][y]) return first = false, i = j, go_left(y, i, LEFT);
return go_left(y, i, RIGHT);
}
int go_left(int x, int y, Info& i, int o, int l, int r)
{
if (r <= x) {
Info j = first ? v[o] : merge(v[o], i, f[r][0], f[r][1]);
if (j.x[0][y] || j.x[1][y]) return first = false, i = j, -1;
return go_left(y, i, o, l, r);
}
int m = (l+r)/2;
if (x <= m) return go_left(x, y, i, LEFT);
int t = go_left(x, y, i, RIGHT);
return t == -1 ? go_left(x, y, i, LEFT) : t;
}
P go_left(int x, int y)
{
Info i;
first = true;
int t = go_left(x, y, i, ALL);
assert(i.x[0][y] || i.x[1][y]);
return P(t+1, i.x[1][y]);
}
int go_right(int y, Info& i, int o, int l, int r)
{
if (l == r) {
Info j = first ? v[o] : merge(i, v[o], f[l-1][0], f[l-1][1]);
first = false;
if (j.x[y][0] || j.x[y][1]) return i = j, n;
return r;
}
int m = (l+r)/2;
Info j = first ? v[o*2] : merge(i, v[o*2], f[l-1][0], f[l-1][1]);
if (j.x[y][0] || j.x[y][1]) return first = false, i = j, go_right(y, i, RIGHT);
return go_right(y, i, LEFT);
}
int go_right(int x, int y, Info& i, int o, int l, int r)
{
if (l >= x) {
Info j = first ? v[o] : merge(i, v[o], f[l-1][0], f[l-1][1]);
if (j.x[y][0] || j.x[y][1]) return first = false, i = j, n;
return go_right(y, i, o, l, r);
}
int m = (l+r)/2;
if (x > m) return go_right(x, y, i, RIGHT);
int t = go_right(x, y, i, LEFT);
return t == n ? go_right(x, y, i, RIGHT) : t;
}
P go_right(int x, int y)
{
Info i;
first = true;
int t = go_right(x, y, i, ALL);
assert(i.x[y][0] || i.x[y][1]);
return P(t-1, i.x[y][1]);
}
Info query(int L, int R, int o, int l, int r)
{
if (L <= l && r <= R) return v[o];
int m = (l+r)/2;
if (R <= m) return query(L, R, LEFT);
if (L > m) return query(L, R, RIGHT);
return merge(query(L, R, LEFT), query(L, R, RIGHT), f[m][0], f[m][1]);
}
void refresh(int p, int o, int l, int r)
{
int m = (l+r)/2;
if (p < m) refresh(p, LEFT);
else if (p > m) refresh(p, RIGHT);
up(o, m);
}
void modify(int p, bool x, int o, int l, int r)
{
if (l == r) return v[o] = Info(x), void();
int m = (l+r)/2;
if (p <= m) modify(p, x, LEFT);
else modify(p, x, RIGHT);
up(o, m);
}
bool query(int x1, int y1, int x2, int y2)
{
P l = go_left(x1, y1), r = go_right(x2, y2);
Info i = query(l.first, r.first, ALL);
return i.x[l.second][r.second];
}
} T;
int main()
{
scanf("%d", &n);
T.build(ALL);
char s[10];
while (scanf("%s", s) == 1) {
if (s[0] == 'E') break;
int r1, c1, r2, c2;
scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
--r1, --c1, --r2, --c2;
if (c1 > c2) swap(r1, r2), swap(c1, c2);
if (s[0] == 'A') {
puts(T.query(c1, r1, c2, r2) ? "Y" : "N");
} else {
bool t = s[0] == 'O';
if (r1 == r2) {
f[c1][r1] = t;
T.refresh(c1, ALL);
} else {
T.modify(c1, t, ALL);
}
}
}
return 0;
}