けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 179 F - Simplified Reversi (青色, 600 点)

早速遅延セグ木があればできる問題来た!!
AC Library の出番かと思った!!!

問題へのリンク

問題概要

 N マス、横  N マスのグリッドがあり、はじめグリッドの中央  (N−2) \times (N−2) マスには黒い石が 1 個ずつ置いてあり、下辺と右辺の計  2N−1 マスには白い石が 1 個ずつ置いてある。

以下の  Q 個のクエリをすべて処理し終えたあとに、グリッド上に残っている黒い石の個数を答えよ。

  • 1  x:マス  (1, x) に白い石を置く。オセロルールで黒い石をひっくり返す。
  • 2  x:マス  (x, 1) に白い石を置く。オセロルールで黒い石をひっくり返す。

制約

  •  N, Q \le 2 \times 10^{5}

考えたこと

すべて 0-indexed にして考える。図のような配置になったとき、1 のところに置くか 2 のところに置くかでひっくり返す個数も変わってくる。このような状況を上手に扱う必要がある。

f:id:drken1215:20200920023345p:plain

そこで、以下の情報を常時管理したい

  • 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 と更新する

しかしこのままでは  O(NQ) の計算量を要するので工夫が必要。

解法 (1):yoko, tate がもう更新されなくなる領域に着目

よく考えると、下図で赤く囲った「最も左上の黒マス長方形領域」以外にアタックするクエリに対しては、yoko, tate の更新が起きないことがわかる。

このことを深めて、データの持ち方を次のように修正する

  • 上から何行分が剥き出しかを表す変数 R (R 行目が白行とする)
  • 左から何列分が剥き出しかを表す変数 C (C 列目が白列とする)
  • yoko[ r ] := r (> R) 行目において初めて白が登場するのは左から何列目か
  • tate[ c ] := c (> C) 列目において初めて白が登場するのは上から何行目か

つまり、yoko, tate の値を更新するのは「剥き出しではなくなった部分」のみに限ることにする。そうすると、どの行・列についても、yoko, tate の更新が発生するのは高々 1 回のみなので、全体の計算量は  O(N + Q) となる。

f:id:drken1215:20200920024250p:plain

#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 の値を取得する

遅延セグ木を用いれば、これらをともに  O(\log N) で実現できる。よってクエリ全体を  O(N + Q \log N) の計算量で処理できる。

#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;
}