はまやんはまやんはまやん

hamayanhamayan's blog

Thor [Codeforces 366 : Div2 C, Div1 A]

問題

http://codeforces.com/contest/705/problem/C

n種類のアプリがあるスマホがある。
時系列順でq個のクエリが与えられる。
各クエリの処理後、未読の通知は何個あるかそれぞれ答える。

クエリは以下の3種ある。
1. アプリ x が通知を出す
2. これより前にアプリ x が出した通知を既読にする
3. 全ての通知の先頭 t 個の通知を既読にする(未読の先頭t個ではない)

1 <= n,q <= 3*10^5

考察

1. 時系列があるのでソートはできない
2. 後ろから処理してくとうまくいく典型パターン??
3. 無理そう

4. とりあえず愚直解考えてみよう
5. バッファを用意する
6. クエリ1の時はバッファの最後尾にそのアプリ番号を入れる
7. クエリ2,3の時はバッファを最初から最後まで走査して、該当するやつを既読にする
8. 各クエリの最後にバッファを走査して、未読を数えて出力
9. これだと多分 O(q^2)

10. 既読にする動作は1回だけなので、全部走査するのは無駄っぽい
11. バッファの他に各アプリでバッファに入ってる添字を保存する集合を作る
12. クエリ1で追加するときにこっちにも追加しておくことでクエリ2の探す処理を高速化できる
13. 他にもバッファのどこまでが既読になっているかを保存しておく
14. こうすることでクエリ3での既読処理の時に同じ領域を2回確認することが無くなる
15. これでバッファの更新処理がだいぶ早くなる

16. クエリ前の既読数に対して、クエリ1なら+1でクエリ2,3なら既読にした分減る
17. 前のクエリでの答えから次のクエリの答えを求めることで、全走査がなく高速になる

18. この辺の工夫をすると通る

実装

http://codeforces.com/contest/705/submission/19711297

int n, q;
//-----------------------------------------------------------------
int buf[301010];
int bl = 0, br = 0;
set<int> idx[301010];
//-----------------------------------------------------------------
int main() {
	cin >> n >> q;
	
	int ans = 0;
	rep(i, 0, q) {
		int t, x;
		scanf("%d %d", &t, &x);

		if (t == 1) {
			buf[br] = x;
			idx[x].insert(br);
			br++;
			ans++;
		} else if (t == 2) {
			for (int i : idx[x]) {
				buf[i] = 0;
				ans--;
			}
			idx[x].clear();
		} else {
			if (bl < x) {
				rep(i, bl, x) if (buf[i]) {
					idx[buf[i]].erase(i);
					buf[i] = 0;
					ans--;
				}
				bl = x;
			}
		}

		printf("%d\n", ans);
	}
}