読者です 読者をやめる 読者になる 読者になる

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

問題

codeforces.com

考察

「任意の状態に戻れる」という処理を実現するのがキモになります。

最初に思いつくのは、各状態での本棚がどうだったかを覚えておくことですが、 O(nmq) のメモリが必要なので実装できません。 ではtype4のクエリが来るたびに1から計算すればいいかのかというと、メモリは O(nm)だけで済みますが、運が悪いと実行時間は O(q^{2})くらい掛かってしまいTLEします。

さて、ここまではクエリを来た順に処理していましたが、求める順番はバラバラでも構わないです(最後に元の順番で出力すれば)。 そこで、状態を順番に辿るような木を作ってdfsをし各ノードで答えを求めれば、持つべき状態は1つで済み、辿るのはクエリ数のみなので実行時間も大丈夫そうです。

各ノードでの答えは、直前の状態での答えを利用し O(m)で求めることができます。 計算量は O(nm)で間に合いました。

コード

const int MAX_Q = (int) (1e5) + 10;
vvi graph(MAX_Q + 1);
vi ans(MAX_Q + 1, 0);
vector<vector<bool>> state(1001, vector<bool>(1001, false));
vector<pair<int, pii>> queries(MAX_Q + 1);
int n, m;

void dfs(int v) {
    tr(it, graph[v]) {
        auto qu = queries[*it];
        if (qu.first == 1) {
            int r = qu.second.first;
            int c = qu.second.second;
            if (state[r][c]) {
                ans[*it] = ans[v];
                dfs(*it);
            } else {
                state[r][c] = true;
                ans[*it] = ans[v] + 1;
                dfs(*it);
                state[r][c] = false;
            }
        } else if (qu.first == 2) {
            int r = qu.second.first;
            int c = qu.second.second;
            if (!state[r][c]) {
                ans[*it] = ans[v];
                dfs(*it);
            } else {
                state[r][c] = false;
                ans[*it] = ans[v] - 1;
                dfs(*it);
                state[r][c] = true;
            }
        } else if (qu.first == 3) {
            int r = qu.second.first;
            int f2t = 0, t2f = 0;
            rep(i, m) {
                state[r][i] ? t2f++ : f2t++;
                state[r][i] = !state[r][i];
            }
            ans[*it] = ans[v] + (f2t - t2f);
            dfs(*it);
            rep(i, m)state[r][i] = !state[r][i];
        } else {
            ans[*it] = ans[v];
            dfs(*it);
        }

    }
}

int main() {
    int q;
    cin >> n >> m >> q;

    int now = 0;
    REP(i, 1, q + 1) {
        int a;
        cin >> a;
        if (a == 1 || a == 2) {
            int b, c;
            cin >> b >> c;
            --b, --c;
            queries[i] = mp(a, mp(b, c));
            graph[now].push_back(i);
        } else if (a == 3) {
            int b;
            cin >> b;
            --b;
            queries[i] = mp(a, mp(b, 0));
            graph[now].push_back(i);
        } else {
            int b;
            cin >> b;
            queries[i] = mp(a, mp(b, 0));
            graph[b].push_back(i);
        }

        now = i;
    }

    dfs(0);

    REP(i, 1, q + 1)
        cout << ans[i] << endl;

    return 0;
}