P6492 [COCI2010-2011#6] STEP - 洛谷
题目大意：维护一段 01 串，支持单点修改，每次修改后求最长的「\(\texttt{01010101}\dots\)」 的长度。
下文把 「\(\texttt{01010101}\dots\)」称为「合法区间」，\(k\) 为区间 \([l, r]\) 编号，\(lk, rk\) 为 \([l, r]\) 左右子区间编号。
考虑用线段树进行维护。我们用 \(fl(k), fr(k)\) 别表示区间 \([l, r]\) 的 01 情况，\(tl(k), tr(k)\) 分别表示区间 \([l, r]\) 中 \(l,r\) 在内的合法区间的最大长度，\(t(k)\) 表示区间 \([l, r]\) 的合法区间的最大长度。
则合并时：
- \(fl(k) = fl(lk), fr(k) = fr(rk)\)。
- 如果 \(fr(lk) \ne fl(rk)\) 则区间可以合并，\(t(k) = \max \left \{ t(lk), t(rk), tr(lk) + tl(rk) \right \}\)；否则 \(t(k) = \max \left \{ t(lk), t(rk) \right \}\)。
- 如果 \(tl(k)\) 等于区间长度且合法区间可以合并，则 \(tl(k) = tl(lk) = tl(rk)\)，否则 \(tl(k) = tl(lk)\)。\(tr(k)\) 同理。
更新时只反转 \(fl, fr\) 即可。时间复杂度 \(O(n \log n)\)。
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int N = 200010, N4 = N * 4;
int n, q;
int tr[N4], tl[N4], fl[N4], fr[N4], t[N4];
void build(int l, int r, int k) {
if(l == r) {
fl[k] = fr[k] = 0;
t[k] = tl[k] = tr[k] = 1;
return;
}
int mid = (l + r) >> 1, lk = k << 1, rk = lk | 1;
build(l, mid, lk); build(mid + 1, r, rk);
fl[k] = fl[lk], fr[k] = fr[rk];
t[k] = max(t[lk], t[rk]);
if(fr[lk] != fl[rk]) t[k] = max(t[k], tl[rk] + tr[lk]);
tl[k] = tl[lk], tr[k] = tr[rk];
if(tl[lk] == mid - l + 1 && fr[lk] != fl[rk]) tl[k] += tl[rk];
if(tr[rk] == r - mid && fr[lk] != fl[rk]) tr[k] += tr[lk];
}
void upd(int l, int r, int k, int L, int R) {
if(L <= l && r <= R) {
fl[k] = !fl[k]; fr[k] = !fr[k];
return;
}
int mid = (l + r) >> 1, lk = k << 1, rk = lk | 1;
if(L <= mid) upd(l, mid, lk, L, R);
if(mid < R) upd(mid + 1, r, rk, L, R);
fl[k] = fl[lk], fr[k] = fr[rk];
t[k] = max(t[lk], t[rk]);
if(fr[lk] != fl[rk]) t[k] = max(t[k], tl[rk] + tr[lk]);
tl[k] = tl[lk], tr[k] = tr[rk];
if(tl[lk] == mid - l + 1 && fr[lk] != fl[rk]) tl[k] += tl[rk];
if(tr[rk] == r - mid && fr[lk] != fl[rk]) tr[k] += tr[lk];
}
int main() {
scanf("%d%d", &n, &q);
build(1, n, 1);
while(q--){
int x; scanf("%d", &x);
upd(1, n, 1, x, x);
printf("%d\n", t[1]);
}
return 0;
}