遅延評価セグメント木の練習問題！
問題概要
0 と 1 のみからなる長さ の文字列
が与えられる。次の 2 種類のクエリに答えよ。
- クエリ (
1 L R)：文字列の区間
内における、1 が連続する区間の長さの最大値を答えよ
- クエリ (
2 L R)：文字列
制約
考えたこと
まず、クエリ 1 のみならば、次のデータをノードに持たせたセグメント木で解けそうだ。
left_one：そのセグ木ノードの表す区間において、左端から何個の 1 が連続しているかright_one：そのセグ木ノードの表す区間において、右端から何個の 1 が連続しているかone：そのセグ木ノードの表す区間における、1 の連続する長さの最大値
ノードとノードを合成する関数 op(x, y) は次のように実現できる。
- 合成後の
left_one：xが 0 を含むならばx.left_one、含まないならばx.one + y.left_one - 合成後の
right_one：yが 0 を含むならばy.right_one、含まないならばx.right_one + y.one - 合成後の
one：max({x.one, x.right_one + y.left_one, y.one})
なお、x や y が 0 を含むかどうかの判別には、さらに追加のデータが必要で、それは次の「区間 flip」で用意するデータ zero で賄えることとなる。
区間 flip
今回は区間 flip があるので、遅延評価セグ木が使えそうだ。区間 flip を実現するためには、上のデータに加えて「0 に関する情報」も必要になる。具体的には
left_one：そのセグ木ノードの表す区間において、左端から何個の 1 が連続しているかleft_zero：そのセグ木ノードの表す区間において、左端から何個の 0 が連続しているかright_one：そのセグ木ノードの表す区間において、右端から何個の 1 が連続しているかright_zero：そのセグ木ノードの表す区間において、右端から何個の 0 が連続しているかone：そのセグ木ノードの表す区間における、1 の連続する長さの最大値zero：そのセグ木ノードの表す区間における、0 の連続する長さの最大値
また、遅延評価パラメータの値は 0 か 1 で OK (0 は何もしない、1 は flip をする)。
まとめると、次のコードのように実装できる。
コード
#include <bits/stdc++.h> using namespace std; // Lazy Segment Tree template<class Monoid, class Action> struct LazySegmentTree { // various function types using FuncOperator = function<Monoid(Monoid, Monoid)>; using FuncMapping = function<Monoid(Action, Monoid)>; using FuncComposition = function<Action(Action, Action)>; // core member int N; FuncOperator OP; FuncMapping MAPPING; FuncComposition COMPOSITION; Monoid IDENTITY_MONOID; Action IDENTITY_ACTION; // inner data int log, offset; vector<Monoid> dat; vector<Action> lazy; // constructor LazySegmentTree() {} LazySegmentTree(int n, const FuncOperator op, const FuncMapping mapping, const FuncComposition composition, const Monoid &identity_monoid, const Action &identity_action) { init(n, op, mapping, composition, identity_monoid, identity_action); } LazySegmentTree(const vector<Monoid> &v, const FuncOperator op, const FuncMapping mapping, const FuncComposition composition, const Monoid &identity_monoid, const Action &identity_action) { init(v, op, mapping, composition, identity_monoid, identity_action); } void init(int n, const FuncOperator op, const FuncMapping mapping, const FuncComposition composition, const Monoid &identity_monoid, const Action &identity_action) { N = n, OP = op, MAPPING = mapping, COMPOSITION = composition; IDENTITY_MONOID = identity_monoid, IDENTITY_ACTION = identity_action; log = 0, offset = 1; while (offset < N) ++log, offset <<= 1; dat.assign(offset * 2, IDENTITY_MONOID); lazy.assign(offset * 2, IDENTITY_ACTION); } void init(const vector<Monoid> &v, const FuncOperator op, const FuncMapping mapping, const FuncComposition composition, const Monoid &identity_monoid, const Action &identity_action) { init((int)v.size(), op, mapping, composition, identity_monoid, identity_action); build(v); } void build(const vector<Monoid> &v) { assert(N == (int)v.size()); for (int i = 0; i < N; ++i) dat[i + offset] = v[i]; for (int k = offset - 1; k > 0; --k) pull_dat(k); } int size() const { return N; } // basic functions for lazy segment tree void pull_dat(int k) { dat[k] = OP(dat[k * 2], dat[k * 2 + 1]); } void apply_lazy(int k, const Action &f) { dat[k] = MAPPING(f, dat[k]); if (k < offset) lazy[k] = COMPOSITION(f, lazy[k]); } void push_lazy(int k) { if (lazy[k] == IDENTITY_ACTION) return; apply_lazy(k * 2, lazy[k]); apply_lazy(k * 2 + 1, lazy[k]); lazy[k] = IDENTITY_ACTION; } void pull_dat_deep(int k) { for (int h = 1; h <= log; ++h) pull_dat(k >> h); } void push_lazy_deep(int k) { for (int h = log; h >= 1; --h) push_lazy(k >> h); } // setter and getter, update A[i], i is 0-indexed, O(log N) void set(int i, const Monoid &v) { assert(0 <= i && i < N); int k = i + offset; push_lazy_deep(k); dat[k] = v; pull_dat_deep(k); } Monoid get(int i) { assert(0 <= i && i < N); int k = i + offset; push_lazy_deep(k); return dat[k]; } Monoid operator [] (int i) { return get(i); } // apply f for index i void apply(int i, const Action &f) { assert(0 <= i && i < N); int k = i + offset; push_lazy_deep(k); dat[k] = MAPPING(f, dat[k]); pull_dat_deep(k); } // apply f for interval [l, r) void apply(int l, int r, const Action &f) { assert(0 <= l && l <= r && r <= N); if (l == r) return; l += offset, r += offset; for (int h = log; h >= 1; --h) { if (((l >> h) << h) != l) push_lazy(l >> h); if (((r >> h) << h) != r) push_lazy((r - 1) >> h); } int original_l = l, original_r = r; for (; l < r; l >>= 1, r >>= 1) { if (l & 1) apply_lazy(l++, f); if (r & 1) apply_lazy(--r, f); } l = original_l, r = original_r; for (int h = 1; h <= log; ++h) { if (((l >> h) << h) != l) pull_dat(l >> h); if (((r >> h) << h) != r) pull_dat((r - 1) >> h); } } // get prod of interval [l, r) Monoid prod(int l, int r) { assert(0 <= l && l <= r && r <= N); if (l == r) return IDENTITY_MONOID; l += offset, r += offset; for (int h = log; h >= 1; --h) { if (((l >> h) << h) != l) push_lazy(l >> h); if (((r >> h) << h) != r) push_lazy(r >> h); } Monoid val_left = IDENTITY_MONOID, val_right = IDENTITY_MONOID; for (; l < r; l >>= 1, r >>= 1) { if (l & 1) val_left = OP(val_left, dat[l++]); if (r & 1) val_right = OP(dat[--r], val_right); } return OP(val_left, val_right); } Monoid all_prod() { return dat[1]; } // get max r that f(get(l, r)) = True (0-indexed), O(log N) // f(IDENTITY) need to be True int max_right(const function<bool(Monoid)> f, int l = 0) { if (l == N) return N; l += offset; push_lazy_deep(l); Monoid sum = IDENTITY_MONOID; do { while (l % 2 == 0) l >>= 1; if (!f(OP(sum, dat[l]))) { while (l < offset) { push_lazy(l); l = l * 2; if (f(OP(sum, dat[l]))) { sum = OP(sum, dat[l]); ++l; } } return l - offset; } sum = OP(sum, dat[l]); ++l; } while ((l & -l) != l); // stop if l = 2^e return N; } // get min l that f(get(l, r)) = True (0-indexed), O(log N) // f(IDENTITY) need to be True int min_left(const function<bool(Monoid)> f, int r = -1) { if (r == 0) return 0; if (r == -1) r = N; r += offset; push_lazy_deep(r - 1); Monoid sum = IDENTITY_MONOID; do { --r; while (r > 1 && (r % 2)) r >>= 1; if (!f(OP(dat[r], sum))) { while (r < offset) { push_lazy(r); r = r * 2 + 1; if (f(OP(dat[r], sum))) { sum = OP(dat[r], sum); --r; } } return r + 1 - offset; } sum = OP(dat[r], sum); } while ((r & -r) != r); return 0; } // debug stream friend ostream& operator << (ostream &s, LazySegmentTree seg) { for (int i = 0; i < (int)seg.size(); ++i) { s << seg[i]; if (i != (int)seg.size() - 1) s << " "; } return s; } // dump void dump() { for (int i = 0; i <= log; ++i) { for (int j = (1 << i); j < (1 << (i + 1)); ++j) { cout << "{" << dat[j] << "," << lazy[j] << "} "; } cout << endl; } } }; struct Node { int left_zero, left_one, right_zero, right_one, zero, one; Node() {} Node(int lz, int lo, int rz, int ro, int z, int o) : left_zero(lz), left_one(lo), right_zero(rz), right_one(ro), zero(z), one(o) {} }; ostream &operator << (ostream &s, Node x) { return s << "{" << x.zero << ", " << x.one << "}"; } int main() { int N, Q; string S; cin >> N >> Q >> S; vector<Node> ini(N); for (int i = 0; i < N; ++i) { if (S[i] == '0') ini[i] = Node(1, 0, 1, 0, 1, 0); else ini[i] = Node(0, 1, 0, 1, 0, 1); } Node identity_monoid = Node(-1, -1, -1, -1, -1, -1); int identity_action = 0; auto op = [&](Node x, Node y) -> Node { if (x.one == -1) return y; if (y.one == -1) return x; Node res; res.left_zero = (x.one ? x.left_zero : x.zero + y.left_zero); res.left_one = (x.zero ? x.left_one : x.one + y.left_one); res.right_zero = (y.one ? y.right_zero : x.right_zero + y.zero); res.right_one = (y.zero ? y.right_one : x.right_one + y.one); res.zero = max({x.zero, x.right_zero + y.left_zero, y.zero}); res.one = max({x.one, x.right_one + y.left_one, y.one}); return res; }; auto mapping = [&](int f, Node x) -> Node { if (f) return Node(x.left_one, x.left_zero, x.right_one, x.right_zero, x.one, x.zero); else return x; }; auto composition = [&](int g, int f) -> int { if (g) return !f; else return f; }; LazySegmentTree<Node,int> seg(ini, op, mapping, composition, identity_monoid, identity_action); while (Q--) { int c, L, R; cin >> c >> L >> R; --L; if (c == 1) { seg.apply(L, R, 1); } else { cout << seg.prod(L, R).one << endl; } } }
