Codeforces Round #368 (Div. 2) D. Persistent Bookcase
これ普通に頭良いと思うんだけどみんな解いてるんだよなぁ…
問題
最初すべてのセルが塗られていないグリッドが与えられる。以下の 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; }