早速遅延セグ木があればできる問題来た！！
AC Library の出番かと思った！！！
問題概要
縦 マス、横
マスのグリッドがあり、はじめグリッドの中央
マスには黒い石が 1 個ずつ置いてあり、下辺と右辺の計
マスには白い石が 1 個ずつ置いてある。
以下の 個のクエリをすべて処理し終えたあとに、グリッド上に残っている黒い石の個数を答えよ。
- 1
：マス
に白い石を置く。オセロルールで黒い石をひっくり返す。
- 2
に白い石を置く。オセロルールで黒い石をひっくり返す。
制約
考えたこと
すべて 0-indexed にして考える。図のような配置になったとき、1 のところに置くか 2 のところに置くかでひっくり返す個数も変わってくる。このような状況を上手に扱う必要がある。
そこで、以下の情報を常時管理したい
- yoko[ r ] := r 行目において初めて白が登場するのは左から何列目か (初期値は N-1)
- tate[ c ] := c 列目において初めて白が登場するのは上から何行目か (初期値は N-1)
この情報を持っておけば、次のように考えることができる。
- クエリ 1 (x) に対しては、r = 1, 2, ..., tate[ x ] - 1 に対して
- マス (r, x) を白にひっくり返す
- このとき黒マスは tate[ x ] - 1 個だけ減少する
- このとき、もし yoko[ r ] の値が x より大きいならば、yoko[ r ] = x と更新する
- クエリ 2 (x) に対しては、c = 1, 2, ..., yoko[ x ] - 1 に対して
- マス (x, c) を白にひっくり返す
- このとき白マスは yoko[ x ] - 1 個だけ減少する
- このとき、もし tate[ c ] の値が x より大きいならば、tate[ c ] = x と更新する
しかしこのままでは の計算量を要するので工夫が必要。
解法 (1)：yoko, tate がもう更新されなくなる領域に着目
よく考えると、下図で赤く囲った「最も左上の黒マス長方形領域」以外にアタックするクエリに対しては、yoko, tate の更新が起きないことがわかる。
このことを深めて、データの持ち方を次のように修正する
- 上から何行分が剥き出しかを表す変数 R (R 行目が白行とする)
- 左から何列分が剥き出しかを表す変数 C (C 列目が白列とする)
- yoko[ r ] := r (> R) 行目において初めて白が登場するのは左から何列目か
- tate[ c ] := c (> C) 列目において初めて白が登場するのは上から何行目か
つまり、yoko, tate の値を更新するのは「剥き出しではなくなった部分」のみに限ることにする。そうすると、どの行・列についても、yoko, tate の更新が発生するのは高々 1 回のみなので、全体の計算量は となる。
#include <bits/stdc++.h> using namespace std; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } int main() { long long N, Q; cin >> N >> Q; int R = N-1, C = N-1; long long res = (N - 2) * (N - 2); vector<long long> yoko(N, N-1), tate(N, N-1); for (int q = 0; q < Q; ++q) { int type, x; cin >> type >> x; --x; // (0, x) に置く if (type == 1) { if (x > C) res -= tate[x] - 1; else { res -= R - 1; tate[x] = 0; for (int c = C-1; c > x; --c) tate[c] = R; C = x; } } // (x, 0) に置く else { if (x > R) res -= yoko[x] - 1; else { res -= C - 1; yoko[x] = 0; for (int r = R-1; r > x; --r) yoko[r] = C; R = x; } } } cout << res << endl; }
解法 (2)：遅延セグ木で殴る
解法 (1) では、yoko, tate の更新を最後だけにする (剥き出しでなくなる瞬間だけにする) ことで計算量を削減した。しかし、配列 yoko, tate をセグ木に乗せることで、真正面からクエリ処理することもできる。具体的には次のことができるセグ木を用意する。
- 区間更新クエリ (l, r, v)：配列の区間 [l, r) に属する値 x に対して chmin(x, v) とする
- 一点取得クエリ (x)：配列の index x の値を取得する
遅延セグ木を用いれば、これらをともに で実現できる。よってクエリ全体を
の計算量で処理できる。
#include <bits/stdc++.h> using namespace std; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } // Segment Tree template<class Monoid, class Action> struct SegTree { using FuncMonoid = function< Monoid(Monoid, Monoid) >; using FuncAction = function< void(Monoid&, Action) >; using FuncLazy = function< void(Action&, Action) >; FuncMonoid FM; FuncAction FA; FuncLazy FL; Monoid UNITY_MONOID; Action UNITY_LAZY; int SIZE, HEIGHT; vector<Monoid> dat; vector<Action> lazy; SegTree() { } SegTree(int n, const FuncMonoid fm, const FuncAction fa, const FuncLazy fl, const Monoid &unity_monoid, const Action &unity_lazy) : FM(fm), FA(fa), FL(fl), UNITY_MONOID(unity_monoid), UNITY_LAZY(unity_lazy) { SIZE = 1; HEIGHT = 0; while (SIZE < n) SIZE <<= 1, ++HEIGHT; dat.assign(SIZE * 2, UNITY_MONOID); lazy.assign(SIZE * 2, UNITY_LAZY); } void init(int n, const FuncMonoid fm, const FuncAction fa, const FuncLazy fl, const Monoid &unity_monoid, const Action &unity_lazy) { FM = fm; FA = fa; FL = fl; UNITY_MONOID = unity_monoid; UNITY_LAZY = unity_lazy; SIZE = 1; HEIGHT = 0; while (SIZE < n) SIZE <<= 1, ++HEIGHT; dat.assign(SIZE * 2, UNITY_MONOID); lazy.assign(SIZE * 2, UNITY_LAZY); } /* set, a is 0-indexed */ void set(int a, const Monoid &v) { dat[a + SIZE] = v; } void build() { for (int k = SIZE - 1; k > 0; --k) dat[k] = FM(dat[k*2], dat[k*2+1]); } /* update [a, b) */ inline void evaluate(int k) { if (lazy[k] == UNITY_LAZY) return; if (k < SIZE) FL(lazy[k*2], lazy[k]), FL(lazy[k*2+1], lazy[k]); FA(dat[k], lazy[k]); lazy[k] = UNITY_LAZY; } inline void update(int a, int b, const Action &v, int k, int l, int r) { evaluate(k); if (a <= l && r <= b) FL(lazy[k], v), evaluate(k); else if (a < r && l < b) { update(a, b, v, k*2, l, (l+r)>>1), update(a, b, v, k*2+1, (l+r)>>1, r); dat[k] = FM(dat[k*2], dat[k*2+1]); } } inline void update(int a, int b, const Action &v) { update(a, b, v, 1, 0, SIZE); } /* get [a, b) */ inline Monoid get(int a, int b, int k, int l, int r) { evaluate(k); if (a <= l && r <= b) return dat[k]; else if (a < r && l < b) return FM(get(a, b, k*2, l, (l+r)>>1), get(a, b, k*2+1, (l+r)>>1, r)); else return UNITY_MONOID; } inline Monoid get(int a, int b) { return get(a, b, 1, 0, SIZE); } inline Monoid operator [] (int a) { return get(a, a+1); } /* debug */ void print() { for (int i = 0; i < SIZE; ++i) { cout << (*this)[i]; if (i != SIZE) cout << ","; } cout << endl; } }; int main() { long long N, Q; cin >> N >> Q; long long res = (N - 2) * (N - 2); auto fm = [](long long a, long long b) { return min(a, b); }; // なんでもいい auto fa = [](long long &a, long long d) { chmin(a, d); }; auto fl = [](long long &d, long long e) { chmin(d, e); }; SegTree<long long, long long> yoko(N, fm, fa, fl, N-1, N-1); SegTree<long long, long long> tate(N, fm, fa, fl, N-1, N-1); for (int _ = 0; _ < Q; ++_) { int type, a, val; cin >> type >> a; --a; if (type == 1) { val = yoko.get(a, a + 1); res -= val - 1; tate.update(0, val, a); tate.update(val, val + 1, 0); } else { val = tate.get(a, a + 1); res -= val - 1; yoko.update(0, val, a); yoko.update(val, val + 1, 0); } } cout << res << endl; }
