线段树结点结构:
bl,br,ba 分别表示包括左端点黑石子的连续长度,包括右端点黑石子的连续长度,区间中黑石子的最大连续长度
wl,wr,wa 分别表示包括左端点白石子的连续长度,包括右端点白石子的连续长度,区间中白石子的最大连续长度
ta 表示结点的子结点是否需要更新
对于区间[a,b]的更新操作:
首先找到线段树中相应的区间,将黑变白、白变黑实际上就是把 bl,br,ba 和 wl,wr,wa 互换。但是不对这个区间的子区间再进行更新(如果这样做的话时间复杂度就会达到O(n)),而是将 ta xor 1,记下该区间的子区间没有被跟新,下次如果用到(更新或者查询)该区间的子区间再对其进行更新。对包含被更新区间的所有区间进行更新。
#include <stdio.h> #include <stdlib.h> #include <math.h> #include <string.h> #include <memory.h> #include <string> #include <vector> #include <map> #include <set> #include <queue> #include <algorithm> #include <iostream> using namespace std; const int N = 100005; struct Node { int l, r; int bl, br, ba; int wl, wr, wa; int ta; } st[N*3]; int ary[N]; void Update(int p) { int lp = p * 2, rp = p * 2 + 1; if ((st[p].ba = max(st[lp].ba, st[rp].ba)) < st[lp].br + st[rp].bl) st[p].ba = st[lp].br + st[rp].bl; if ((st[p].wa = max(st[lp].wa, st[rp].wa)) < st[lp].wr + st[rp].wl) st[p].wa = st[lp].wr + st[rp].wl; int ll = st[lp].r - st[lp].l + 1, rl = st[rp].r - st[rp].l + 1; st[p].bl = st[lp].bl; if (st[lp].bl == ll) st[p].bl += st[rp].bl; st[p].wl = st[lp].wl; if (st[lp].wl == ll) st[p].wl += st[rp].wl; st[p].br = st[rp].br; if (st[rp].br == rl) st[p].br += st[lp].br; st[p].wr = st[rp].wr; if (st[rp].wr == rl) st[p].wr += st[lp].wr; } void Change(int p) { swap(st[p].bl, st[p].wl); swap(st[p].br, st[p].wr); swap(st[p].ba, st[p].wa); st[p].ta ^= 1; } void Build(int l, int r, int p) { st[p].l = l; st[p].r = r; st[p].ta = 0; if (l == r) { if (ary[l]) { st[p].bl = st[p].br = st[p].ba = 1; st[p].wl = st[p].wr = st[p].wa = 0; } else { st[p].wl = st[p].wr = st[p].wa = 1; st[p].bl = st[p].br = st[p].ba = 0; } return; } int m = (l + r) / 2; Build(l, m, p * 2); Build(m + 1, r, p * 2 + 1); Update(p); } void Update(int l, int r, int p) { if (st[p].l == l && st[p].r == r) { Change(p); return; } if (st[p].ta) { Change(p * 2); Change(p * 2 + 1); st[p].ta ^= 1; } int m = (st[p].l + st[p].r) / 2; if (r <= m) Update(l, r, p * 2); else if (l > m) Update(l, r, p * 2 + 1); else Update(l, m, p * 2), Update(m + 1, r, p * 2 + 1); Update(p); } int Query(int l, int r, int p) { // printf("%d %d %d\n", p, st[p].ba, st[p].ta); if (st[p].l == l && st[p].r == r) { return st[p].ba; } if (st[p].ta) { Change(p * 2); Change(p * 2 + 1); st[p].ta ^= 1; } int m = (st[p].l + st[p].r) / 2; if (r <= m) return Query(l, r, p * 2); else if (l > m) return Query(l, r, p * 2 + 1); else { int lr = Query(l, m, p * 2); int rr = Query(m + 1, r, p * 2 + 1); return max(max(min(st[p*2].br, lr) + min(st[p*2+1].bl, rr), lr), rr); } } int main() { int n, m, i, a, b, c; while (scanf("%d", &n) != EOF) { for (i = 1; i <= n; i++) scanf("%d", ary + i); Build(1, n, 1); scanf("%d", &m); for (i = 0; i < m; i++) { scanf("%d %d %d", &a, &b, &c); if (a) Update(b, c, 1); else printf("%d\n", Query(b, c, 1)); } } return 0; }