mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #368 (Div. 2) D. Persistent Bookcase

これ普通に頭良いと思うんだけどみんな解いてるんだよなぁ…

問題

codeforces.com

最初すべてのセルが塗られていないグリッドが与えられる。以下の Q 個クエリを処理し, グリッドで黒色のセルの数を出力せよ。

  • i 行 j 列目のセルが白なら黒くする。
  • i 行 j 列目のセルが黒なら白くする。
  • i 行目の白黒を反転させる。
  • クエリの q 個目の状態に戻す。
解法

あらかじめどういうクエリが来るかはわかっているので, 「クエリの q 個目の状態に戻す」というのが来たときどこに戻れば良いかを覚えておけば, 基本的にはクエリの木構造ができています。木構造に合わせて, 素直にクエリを処理していけば O(NQ) 程度でできます。

const int MAXQ = 100100;
int N, M, Q;
int T[MAXQ], I[MAXQ], J[MAXQ];
int ans[MAXQ];
int reff[MAXQ];
vector<int> G[MAXQ];

bool board[1010][1010];
int S;

void dfs(int v) {
    ans[v] = S;
    for (int ch : G[v]) {
        if (T[ch] == 1) {
            bool prv = board[I[ch]][J[ch]];
            if (!board[I[ch]][J[ch]]) {
                S++;
            }
            board[I[ch]][J[ch]] = true;
            dfs(ch);
            board[I[ch]][J[ch]] = prv;
            if (!prv) S--;
        } else if (T[ch] == 2) {
            bool prv = board[I[ch]][J[ch]];
            if (board[I[ch]][J[ch]]) {
                S--;
            }
            board[I[ch]][J[ch]] = false;
            dfs(ch);
            board[I[ch]][J[ch]] = prv;
            if (prv) S++;
        } else if (T[ch] == 3) {
            for (int i = 0; i < M; i++) {
                if (board[I[ch]][i]) {
                    S--;
                    board[I[ch]][i] = false;
                } else {
                    S++;
                    board[I[ch]][i] = true;
                }
            }
            dfs(ch);
            for (int i = 0; i < M; i++) {
                if (board[I[ch]][i]) {
                    S--;
                    board[I[ch]][i] = false;
                } else {
                    S++;
                    board[I[ch]][i] = true;
                }
            }
        } else {
            assert(0);
        }
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M >> Q;
    for (int i = 1; i <= Q; i++) {
        cin >> T[i] >> I[i];
        if (T[i] <= 2) cin >> J[i];
        if (T[i] <= 3) I[i]--; J[i]--;
    }
    int now = 0;
    for (int i = 1; i <= Q; i++) {
        if (T[i] <= 3) {
            G[now].emplace_back(i);
            now = i;
            reff[i] = i;
        } else {
            now = reff[I[i]];
            reff[i] = now;
        }
    }
    dfs(0);
    for (int i = 1; i <= Q; i++) 
        cout << ans[reff[i]] << endl;
    return 0;
}