Codeforces Round #366 (Div. 2) C. Thor

問題

codeforces.com

q 個のクエリが飛んでくる。それぞれのクエリは type, x の二つの整数から構成され,

• type = 1 の時, 種類 x のボールが飛んでくる
• type = 2 の時, 今までに飛んできた種類 x のボールをすべて捨てる
• type = 3 の時, 今まで飛んできたすべてのボールのうち, 最初の x 個のボールを捨てる

それぞれのクエリが投げられた直後, 手元にあるボールの数を求めよ。

解法

D[x]: 種類 x のボールが投げられたタイミングをすべて記録したもの
S[x], T[x]: 種類 x のボールのうち, 手元にあるものの区間([S[x], T[x]) の区間 i について, D[x][i] というボールがある)
memo[i]: i 番目に来たボールはまだ手元にあるか

というようにデータを持っておきます。すると,

• type 1 については, D[x].push_back と T[x]++ でだいたい済む
• type 2 については, [S[x], T[x]) の区間に含まれる i について, memo[D[x][i]] = false にする
• type 3 については, memo[x] までをすべて false にする

ということをやれば良いです。すでに調べたところを二重に調べなければ, これらのクエリはすべて全体として O(Q) で対処可能です。

const int MAXN = 300300;
vi D[MAXN];
int S[MAXN], T[MAXN], R[MAXN];
bool memo[MAXN];

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    int note = 0, ans = 0, last = 0;
    for (int i = 0; i < q; i++) {
        int type, x;
        scanf("%d %d", &type, &x);
        if (type == 1) {
            D[x].push_back(note);
            memo[note] = true;
            //R[note] = x;
            note++;
            ans++;
            T[x]++;
        } else if (type == 2) {
            for (int i = S[x]; i < T[x]; i++) {
                if (memo[D[x][i]]) {
                    ans--;
                    memo[D[x][i]] = false;
                }
            }
            S[x] = T[x];
        } else {
            for (int i = last; i < x; i++) {
                if (memo[i]) {
                    ans--;
                    memo[i] = false;
                    //S[R[i]]++;
                }
            }
            last = max(last, x);
        }
        printf("%d\n", ans);
    }
    return 0;
}

これ 2000 人も解けるのね…