一条 \(n\) 条边,\(n+1\) 个点的链,边有黑有白。若结点 \(a\) 可以到达 \(b\),需要满足 \(a\to b\) 的路径上的边不能有黑的。现给出 \(0\) 时刻边的初始状态,然后随后 \(1\sim q\) 时刻每时刻有一个事件或查询:
对于每一个 \(\texttt{query}\),输出答案。
\(1\le n, q\le 3\times 10^5\)
设一个位置 \(x\) 可以到达的最左侧位置为 \(L(x)\),右侧为 \(R(x)\)。
这里有一个 用 set
维护连续段 的技巧——对于边状态 \(\texttt{0100011}\),可以分段存为:\([1, 1], [2, 2], [3,5], [6, 7]\) 四段。对于一个位置 \(x\),所属段为 \([l, r]\),那么有 \(L(x)=l, R(x)= r\)。(好像可以直接线段树)
当修改时,若将边 \(x\to x+1\) 变为白色,那么段 \([L(x), x],[x+1, R(x+1)]\) 间变为连通,可以将这两段删去,用 \([L(x), R(x+1)]\) 取而代之。对答案的影响?显然所有满足 \(a\in [L(x), x],b\in[x+1, R(x+1)]\) 的点对 \((a, b)\) 的答案都需要更改。
设当前时间为 \(t\),总时间为 \(T\)。
考虑如何将一个点对转化成一个二维点,而这又是本题的关键。这样一来,上面的修改变成了 **矩形加 ** 操作——左下点为 \((L(x), x+1)\),右上为 \((x, R(x))\) 的矩形区域的每个位置加上 \(T-t\),表明 暂定后面时刻都是连通的。
同理,若是白变黑,那么就是矩形减 \(T-t\)。表明目前看来,后面都不连通。
那么对于查询,只要获取位置 \((a, b)\) 的值即可。若当前两点是联通的,由于上文是暂定,于是还要把后面减掉,答案 \(-(T-t)\)。
如何高效执行上述两个操作?显然可以 CDQ 但我老写炸。不如树套树吧。把矩形修改差分成四个,单点询问转化成区域查询即可。
时空复杂度 \(O(n\log^2 n)\)。
/*
* Author : _Wallace_
* Source : https://www.cnblogs.com/-Wallace-/
* Problem : LOJ#3146 APIO2019 路灯
*/
#include <cstdio>
#include <set>
using namespace std;
const int MaxN = 3e5 + 5;
int n, N, T;
bool dat[MaxN];
char str[MaxN];
namespace bit_seg {
const int S = MaxN << 9;
int lc[S], rc[S], total = 0, sum[S];
#define mid ((l + r) >> 1)
int root[MaxN];
#define lbt(x) (x & (-x))
void ins(int& x, int p, int v, int l, int r) {
if (!x) x = ++total;
sum[x] += v;
if (l == r) return;
if (p <= mid) ins(lc[x], p, v, l, mid);
else ins(rc[x], p, v, mid + 1, r);
}
void upd(int r, int c, int val) {
for (; r <= n; r += lbt(r)) ins(root[r], c, val, 1, n + 1);
}
void rectAdd(int xl, int yl, int xr, int yr, int val) {
upd(xl, yl, val);
upd(xr + 1, yr + 1, val);
upd(xl, yr + 1, -val);
upd(xr + 1, yl, -val);
}
int get(int x, int ql, int qr, int l, int r) {
if (!x) return 0;
if (ql <= l && r <= qr) return sum[x];
int ret = 0;
if (l <= mid) ret += get(lc[x], ql, qr, l, mid);
if (r > mid) ret += get(rc[x], ql, qr, mid + 1, r);
return ret;
}
int Query(int r, int c) {
int ret = 0;
for (; r; r -= lbt(r)) ret += get(root[r], 1, c, 1, n + 1);
return ret;
}
};
struct interval {
int l, r;
inline interval(int L, int R) : l(L), r(R) { }
inline bool operator < (const interval& x) const { return r < x.r; }
};
set<interval> itv;
typedef set<interval>::iterator Iter;
#include <algorithm>
signed main() {
scanf("%d%d", &n, &T), N = n++;
scanf("%s", str + 1);
for (int i = 1; i <= n; i++)
itv.insert(interval(i, i));
for (int i = 1; i <= N; i++) {
dat[i] = (str[i] == '1');
if (dat[i]) {
Iter it = --itv.lower_bound(interval(0, i + 1));
int L = it->l;
itv.erase(it), itv.erase(interval(i + 1, i + 1));
itv.insert(interval(L, i + 1));
}
}
for (Iter it = itv.begin(); it != itv.end(); it++)
bit_seg::rectAdd(it->l, it->l, it->r, it->r, T);
for (int t = 1; t <= T; t++) {
char opt[10];
int i, a, b;
scanf("%s", opt);
if (opt[0] == 't') {
scanf("%d", &i);
if (dat[i]) {
Iter it = itv.lower_bound(interval(0, i));
int l1 = it->l, r1 = i, l2 = i + 1, r2 = it->r;
bit_seg::rectAdd(l1, l2, r1, r2, -(T - t));
itv.erase(interval(l1, r2));
itv.insert(interval(l1, r1));
itv.insert(interval(l2, r2));
} else {
Iter it = itv.lower_bound(interval(0, i));
int l1 = it->l, r1 = i, l2 = i + 1, r2 = (++it)->r;
bit_seg::rectAdd(l1, l2, r1, r2, T - t);
itv.erase(interval(l1, r1));
itv.erase(interval(l2, r2));
itv.insert(interval(l1, r2));
}
dat[i] ^= 1;
} else {
scanf("%d%d", &a, &b);
int ans = bit_seg::Query(a, b);
if (itv.lower_bound(interval(0, a)) == itv.lower_bound(interval(0, b)))
printf("%d\n", ans - (T - t));
else printf("%d\n", ans);
}
}
}