洛谷 P5618 堵塞的交通
题意
有一个 \(2\times C\) 的网格图，需要维护 \(3\) 种操作。
- 连接相邻的两个格子。
- 将相邻的两个格子断开连接。
- 询问两个格子是否联通。
思路1
考虑分块。
连边时块内使用并查集维护，块与块之间用数组标记。
删边块内的边时暴力重构并查集，块之间的边清零标记。
查询时使用广搜。
从块的四个角开始广搜。
先使用并查集把起点能走到的角入队。
搜索时记录当前点编号和当前块的编号。
每个点可以走向相邻有标记的块的四角，
也可以走向当前块联通的四角（使用并查集判断）。
使用并查集判断终点所在块能被到达的角能否到达终点。
时间复杂度：\(O(n\sqrt n)\)。
代码1
#include <bits/stdc++.h>
#define ID(x,y) (((y)-1)*2+(x)) // x y 写反
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N = 1e6 + 5, M = 1005;
int n, L[M], R[M], id[N], fa[N];
int lu[M], ld[M], ru[M], rd[M];
int lkr[N], lkl[N];
int base, cnt;
vector <pii> E[M], temp;
char op[10];
struct node {int id, kid;};
queue <node> q;
queue <int> Q;
bool can[N];
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return ;
fa[fx] = fy;
}
bool same(int x, int y) {return find(x) == find(y);}
void rebuild(int id, int x = 0, int y = 0) {
lu[id] = ID(1, L[id]), ru[id] = ID(1, R[id]); // x y 写反
ld[id] = ID(2, L[id]), rd[id] = ID(2, R[id]);
for (int i = L[id]; i <= R[id]; i ++)
fa[ID(1, i)] = ID(1, i), fa[ID(2, i)] = ID(2, i);
for (auto e : E[id]) {
if (e.fi == x && e.se == y) continue;
merge(e.fi, e.se);
temp.push_back(e);
}
E[id].swap(temp); temp.clear();
}
void init() {
base = sqrt(n);
for (int i = 1; i <= n; i ++) {
id[i] = (i - 1) / base + 1;
if (!L[id[i]]) L[id[i]] = i;
R[id[i]] = max(R[id[i]], i);
cnt = max(cnt, id[i]);
}
for (int i = 1; i <= cnt; i ++) rebuild(i);
}
void link(int x_1, int y_1, int x_2, int y_2) {
if (ID(x_1, y_1) > ID(x_2, y_2)) swap(x_1, x_2), swap(y_1, y_2);
if (id[y_1] == id[y_2]) {
merge(ID(x_1, y_1), ID(x_2, y_2));
E[id[y_1]].push_back({ID(x_1, y_1), ID(x_2, y_2)});
return ;
}
lkr[ID(x_1, y_1)] = 1;
lkl[ID(x_2, y_2)] = 1;
}
void cut(int x_1, int y_1, int x_2, int y_2) {
if (ID(x_1, y_1) > ID(x_2, y_2)) swap(x_1, x_2), swap(y_1, y_2);
if (id[y_1] == id[y_2]) {
rebuild(id[y_1], ID(x_1, y_1), ID(x_2, y_2));
return ;
}
lkr[ID(x_1, y_1)] = 0;
lkl[ID(x_2, y_2)] = 0;
}
int query(int x_1, int y_1, int x_2, int y_2) { // 思路错
if (same(ID(x_1, y_1), ID(x_2, y_2))) return 1; // 没判
if (same(ID(x_1, y_1), ld[id[y_1]])) q.push({ld[id[y_1]], id[y_1]});
if (same(ID(x_1, y_1), rd[id[y_1]])) q.push({rd[id[y_1]], id[y_1]});
if (same(ID(x_1, y_1), lu[id[y_1]])) q.push({lu[id[y_1]], id[y_1]});
if (same(ID(x_1, y_1), ru[id[y_1]])) q.push({ru[id[y_1]], id[y_1]});
while (!q.empty()) {
node x = q.front(); q.pop();
if (can[x.id]) continue;
can[x.id] = 1; // 标记打错
Q.push(x.id);
if (same(x.id, ld[x.kid])) q.push({ld[x.kid], x.kid});
if (same(x.id, lu[x.kid])) q.push({lu[x.kid], x.kid});
if (same(x.id, rd[x.kid])) q.push({rd[x.kid], x.kid});
if (same(x.id, ru[x.kid])) q.push({ru[x.kid], x.kid});
if (x.id == ld[x.kid]) // ld
if (x.kid > 1 && lkl[x.id])
q.push({rd[x.kid - 1], x.kid - 1});
if (x.id == rd[x.kid]) // rd
if (x.kid < cnt && lkr[x.id])
q.push({ld[x.kid + 1], x.kid + 1});
if (x.id == lu[x.kid]) // lu
if (x.kid > 1 && lkl[x.id])
q.push({ru[x.kid - 1], x.kid - 1});
if (x.id == ru[x.kid]) // ru
if (x.kid < cnt && lkr[x.id])
q.push({lu[x.kid + 1], x.kid + 1});
}
int ok = 0;
if (can[lu[id[y_2]]] && same(lu[id[y_2]], ID(x_2, y_2))) ok = 1;
if (can[ru[id[y_2]]] && same(ru[id[y_2]], ID(x_2, y_2))) ok = 1;
if (can[ld[id[y_2]]] && same(ld[id[y_2]], ID(x_2, y_2))) ok = 1;
if (can[rd[id[y_2]]] && same(rd[id[y_2]], ID(x_2, y_2))) ok = 1;
while (!Q.empty()) can[Q.front()] = 0, Q.pop();
return ok;
}
int main() {
scanf("%d", &n);
init();
while (1) {
scanf("%s", op);
if (op[0] == 'E') break;
if (op[0] == 'O') {
int r1, c1, r2, c2;
scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
link(r1, c1, r2, c2);
}
if (op[0] == 'A') {
int r1, c1, r2, c2;
scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
if (query(r1, c1, r2, c2)) puts("Y");
else puts("N");
}
if (op[0] == 'C') {
int r1, c1, r2, c2;
scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
cut(r1, c1, r2, c2);
}
}
return 0;
}
思路2
使用线段树维护区间连通性。
维护左上角，右上角，左下角，右下角两两之间的连通性。
合并区间时分类讨论绕路的情况。
查询区间 \([l,r]\) 时，从线段树中查出 \([1,l],[l,r],[r,n]\) 三个区间，分类讨论绕路的情况。
修改竖着的边时，走到表示该位置的叶子，直接修改，更新即可。
修改横着 \([pos,pos+1]\) 的边时，只用走到第一个 \(mid=pos\) 的区间，更新该区间即可。
时间复杂度：\(O(n\log n)\)。
代码2
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
bool k[2][N];
struct segt{
struct node {
int Lt, Rt;
bool u, d;
bool l, r;
bool x, y;
} t[N << 2];
friend node operator + (node a, node b) {
node res;
res.Lt = a.Lt, res.Rt = b.Rt;
res.l = a.l || (a.u && k[0][a.Rt] && b.l && k[1][a.Rt] && a.d);
res.r = b.r || (b.u && k[0][a.Rt] && a.r && k[1][a.Rt] && b.d);
res.u = (a.u && k[0][a.Rt] && b.u) || (a.x && k[1][a.Rt] && b.y);
res.d = (a.d && k[1][a.Rt] && b.d) || (a.y && k[0][a.Rt] && b.x);
res.x = (a.u && k[0][a.Rt] && b.x) || (a.x && k[1][a.Rt] && b.d);
res.y = (a.y && k[0][a.Rt] && b.u) || (a.d && k[1][a.Rt] && b.y);
return res;
}
#define ls (p << 1)
#define rs (p << 1 | 1)
void build(int p, int l, int r) {
t[p].Lt = l, t[p].Rt = r;
if (l == r) {
t[p].u = t[p].d = 1;
t[p].l = t[p].r = 0;
t[p].x = t[p].y = 0;
return ;
}
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
t[p] = t[ls] + t[rs];
}
void modify(int p, int id, bool c) {
if (t[p].Lt == t[p].Rt) {
t[p].l = t[p].r = c;
t[p].x = t[p].y = c;
t[p].u = t[p].d = 1;
return ;
}
if (id <= t[ls].Rt) modify(ls, id, c);
else modify(rs, id, c);
t[p] = t[ls] + t[rs];
}
void Modify(int p, int id) {
int mid = (t[p].Lt + t[p].Rt) >> 1;
if (mid > id) Modify(ls, id);
else if (mid < id) Modify(rs, id);
t[p] = t[ls] + t[rs];
}
node query(int p, int l, int r) {
if (l <= t[p].Lt && t[p].Rt <= r) return t[p];
node res; res.Lt = -1;
if (t[ls].Rt >= l) res = query(ls, l, r);
if (t[rs].Lt <= r) {
if (res.Lt == -1) res = query(rs, l, r);
else res = res + query(rs, l, r);
}
return res;
}
} T;
int n;
char op[10];
int main() {
scanf("%d", &n);
T.build(1, 1, n);
while (1) {
scanf("%s", op);
if (op[0] == 'E') break;
if (op[0] == 'O') {
int x_1, y_1, x_2, y_2;
scanf("%d%d%d%d", &x_1, &y_1, &x_2, &y_2);
if (y_1 == y_2) T.modify(1, y_1, 1);
else {
if (y_1 > y_2) swap(y_1, y_2);
k[x_1 - 1][y_1] = 1;
T.Modify(1, y_1);
}
}
if (op[0] == 'C') {
int x_1, y_1, x_2, y_2;
scanf("%d%d%d%d", &x_1, &y_1, &x_2, &y_2);
if (y_1 == y_2) T.modify(1, y_1, 0);
else {
if (y_1 > y_2) swap(y_1, y_2);
k[x_1 - 1][y_1] = 0;
T.Modify(1, y_1);
}
}
if (op[0] == 'A') {
int x_1, y_1, x_2, y_2;
scanf("%d%d%d%d", &x_1, &y_1, &x_2, &y_2);
if (y_1 > y_2) swap(x_1, x_2), swap(y_1, y_2);
segt::node mid = T.query(1, y_1, y_2);
segt::node l = T.query(1, 1, y_1);
segt::node r = T.query(1, y_2, n);
bool ans = 0;
if (x_1 == 1 && x_2 == 1) {
ans |= mid.u, ans |= l.r && mid.y;
ans |= mid.x && r.l, ans |= l.r && mid.d && r.l;
}
if (x_1 == 2 && x_2 == 2) {
ans |= mid.d, ans |= l.r && mid.x;
ans |= l.r && mid.u && r.l, ans |= mid.y && r.l;
}
if (x_1 == 1 && x_2 == 2) {
ans |= mid.x, ans |= l.r && mid.y && r.l;
ans |= l.r && mid.d, ans |= mid.u && r.l;
}
if (x_1 == 2 && x_2 == 1) {
ans |= mid.y, ans |= l.r && mid.u;
ans |= mid.d && r.l, ans |= l.r && mid.x && r.l;
}
puts(ans ? "Y" : "N");
}
}
return 0;
}