题目链接
思路要点
我们称能够相互到达的子段为关键段。
维护关键段可以用线段树维护。
先考虑断开某一个关键段 ([l,r]) 的某一条边 (k)，那么这个操作只对 ([l,k]) 到 ([k+1,r]) 内的答案有贡献。同理加入这条边也只对这两个关键段有贡献。
考虑将这个贡献差分，就得到了：
- 若插入，在第 (i) 个时刻，([l,k]) 到 ([k+1,r]) 内的答案 (-i)
- 若删除，在第 (i) 个时刻，([l,k]) 到 ([k+1,r]) 内的答案 (+i)
一个特判，如果每个询问的最后时刻 (t)，若这两个点是联通的，那么我们需要 (+t)。
接下来，我们将两个关键段抽象成二维坐标系内的 (x) 轴和 (y) 轴，也就是每次在 ((l,k+1,k,r)) 内的矩形进行带权修改。
因此考虑离线分治计算答案，是一个二维数点问题。
时间复杂度 (Theta (nlog^2n))
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 5;
char s[N];
int n, q, etot;
int a[N], ans[N];
bool vis[N];
struct Node {
pair<int, int> bd;
bool tag;
} tr[N << 2];
struct Op {
int t, x1, y1, x2, y2, id, v;
} op[N];
struct Event {
int x, ys, ye, v;
bool operator<(const Event& rhs) const {
return x < rhs.x;
}
} evt[N << 1];
int fw[N];
void pushdown(int x) {
if (tr[x].tag) {
tr[x << 1].bd = tr[x << 1 | 1].bd = tr[x].bd;
tr[x << 1].tag = tr[x << 1 | 1].tag = 1;
tr[x].tag = 0;
}
}
void build(int x, int l, int r) {
if (l == r) {
tr[x].bd = make_pair(l, l);
return;
}
int mid = (l + r) >> 1;
build(x << 1, l, mid);
build(x << 1 | 1, mid + 1, r);
}
void modify(int x, int l, int r, int ql, int qr, pair<int, int> val) {
if (ql <= l && r <= qr) {
tr[x].bd = val;
tr[x].tag = 1;
return;
}
pushdown(x);
int mid = (l + r) >> 1;
if (ql <= mid)
modify(x << 1, l, mid, ql, qr, val);
if (qr > mid)
modify(x << 1 | 1, mid + 1, r, ql, qr, val);
}
pair<int, int> query(int x, int l, int r, int p) {
if (l == r)
return tr[x].bd;
pushdown(x);
int mid = (l + r) >> 1;
if (p <= mid)
return query(x << 1, l, mid, p);
else
return query(x << 1 | 1, mid + 1, r, p);
}
void add(int p, int v) {
for (int i = p; i <= n + 1; i += i & -i)
fw[i] += v;
}
int query(int p) {
int ans = 0;
for (int i = p; i >= 1; i -= i & -i)
ans += fw[i];
return ans;
}
void addEvent(int x, int ys, int ye, int v) {
evt[++etot] = (Event){x, ys, ye, v};
}
void solve(int l, int r) {
if (l == r)
return;
int mid = (l + r) >> 1;
solve(l, mid), solve(mid + 1, r);
etot = 0;
for (int i = l; i <= mid; i++)
if (op[i].t == 1) {
addEvent(op[i].x1, op[i].y1, op[i].y2, op[i].v);
addEvent(op[i].x2 + 1, op[i].y1, op[i].y2, -op[i].v);
}
sort(evt + 1, evt + 1 + etot);
sort(op + mid + 1, op + 1 + r, [](Op a, Op b) {
return a.x1 < b.x1;
});
int pt = 1;
for (int i = mid + 1; i <= r; i++)
if (op[i].t == 2) {
while (pt <= etot && evt[pt].x <= op[i].x1) {
add(evt[pt].ys, evt[pt].v);
add(evt[pt].ye + 1, -evt[pt].v);
pt++;
}
ans[op[i].id] += query(op[i].y1);
}
for (int i = 1; i < pt; i++) {
add(evt[i].ys, -evt[i].v);
add(evt[i].ye + 1, evt[i].v);
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
#endif
scanf("%d %d", &n, &q);
scanf("%s", s);
for (int i = 1; i <= n; i++)
a[i] = s[i - 1] - '0';
build(1, 1, n + 1);
for (int i = 1; i <= n; i++)
if (a[i] == 1 && !vis[i]) {
int it = i;
vis[i] = 1;
while (a[it])
it++, vis[it] = 1;
modify(1, 1, n + 1, i, it, make_pair(i, it));
}
memset(ans, 0, sizeof ans);
memset(vis, 0, sizeof vis);
char opt[10];
for (int i = 1; i <= q; i++) {
scanf("%s", opt);
op[i].t = (opt[0] == 'q' ? 2 : 1);
op[i].id = i;
if (op[i].t == 1) {
int k;
scanf("%d", &k);
if (a[k] == 1) {
pair<int, int> p = query(1, 1, n + 1, k);
op[i].x1 = p.first, op[i].x2 = k;
op[i].y1 = k + 1, op[i].y2 = p.second;
op[i].v = i;
modify(1, 1, n + 1, p.first, k, make_pair(p.first, k));
modify(1, 1, n + 1, k + 1, p.second, make_pair(k + 1, p.second));
} else {
pair<int, int> p1 = query(1, 1, n + 1, k), p2 = query(1, 1, n + 1, k + 1);
op[i].x1 = p1.first, op[i].x2 = k;
op[i].y1 = k + 1, op[i].y2 = p2.second;
op[i].v = -i;
modify(1, 1, n + 1, p1.first, p2.second, make_pair(p1.first, p2.second));
}
a[k] ^= 1;
} else {
scanf("%d %d", &op[i].x1, &op[i].y1);
pair<int, int> p = query(1, 1, n + 1, op[i].x1);
if (p.second >= op[i].y1 && p.first <= op[i].y1)
ans[i] += i;
vis[i] = 1;
}
}
memset(fw, 0, sizeof fw);
solve(1, q);
for (int i = 1; i <= q; i++)
if (vis[i])
printf("%d
", ans[i]);
return 0;
}
后言
- 这道题目充分的运用了数形结合和差分的思想，这可以将每一个操作对整体答案的贡献独立处理。而且更加形象的理解。