「全体に足す」のは難しいから、足す値を別途持っておくというスキル！！！
問題概要
以下の 個のクエリに答えよ。
- クエリタイプ 1：新たに要素 0 を挿入する（重複もあり）
- クエリタイプ 2：すでに挿入されているすべての要素に
を足す
- クエリタイプ 3：すでに挿入されている要素のうち、
以上であるものをすべて削除し、その個数を答える
制約
考えたこと
3 種類のクエリ操作のうち、大変なのはクエリタイプ 2「すべての要素に を足す」だ。これを愚直にやると、全体の計算量が
になってしまうのだ。
一方、クエリタイプ 3 に関しては、よほど変なデータ構造を使わない限り、計算量的には大丈夫。そもそも、クエリ全体を通して挿入される要素の個数が最大 個なので、削除される要素の個数も最大で
個である。削除操作が十分速いデータ構造を用いれば、クエリタイプ 3 の計算量は大丈夫。
クエリタイプ 2「すべての要素に を足す」に対処する
このように「全ての要素に一律に を足す」という場面で、よく使うテクがある。それは
実際に全ての要素に を足すのではなく、「後で足す」という意味を込めた変数（
offset とする）を別途持っておく
という方法だ。遅延評価などとも呼ぶこともある。これを用いると、サンプル 1 は次のように解釈できる。
| クエリ | クエリ後の集合 | offset |
備考 |
|---|---|---|---|
| 1 | {0} | 0 | |
| 2, 15 | {0} | 15 | 15 は集合の要素に足さずに offset に足す |
| 1 | {0, -15} | 15 | offset が 15 なので、0 でなく -15 を挿入する |
| 3, 10 | {-15} | 15 | offset が 15 なので、10 - 15 = -5 以上の数を削除する |
| 2, 20 | {-15} | 35 | offset に 20 を足す |
| 3, 20 | {} | 35 | offset が 35 なので、20 - 35 = -15 以上の数を削除する |
この表の例だと、集合のサイズが小さいので変数 offset のありがたみがあまりない。しかし、集合のサイズが大きくなったとき、クエリタイプ 2 の処理を単に「offset += T」で済ませられるようになることは、計算量的に絶大なメリットとなる。
他のクエリタイプも含めてまとめると、
- クエリタイプ 1：集合に 0 を挿入するのではなく、
-offsetを挿入する - クエリタイプ 2：
offset += Tとする - クエリタイプ 3：集合から
H以上の値を削除するのではなく、H - offset以上の値を削除する
というように修正する。
クエリタイプ 3 について
最後に、クエリタイプ 3「集合から H - offset 以上の値を削除する」を実現する方法を考えよう。いろいろな手があって
- 集合を実現するデータ構造として
priority_queueを使い、集合の最大値がH - offset以上である限り、削除する - 集合を実現するデータ構造として
queueを使い、最も古い時期に挿入された要素がH - offset以上である限り、それを削除する
などが考えられる。下のコードでは後者を採用することにした。その場合の計算量は、クエリ全体を通して となる。
コード
#include <bits/stdc++.h> using namespace std; int main() { long long Q, query_type, T, H; cin >> Q; long long offset = 0; // 伸びた分 queue<long long> que; while (Q--) { cin >> query_type; if (query_type == 1) { que.push(-offset); } else if (query_type == 2) { cin >> T; offset += T; } else { cin >> H; long long res = 0; while (!que.empty() && que.front() + offset >= H) { res++; que.pop(); } cout << res << endl; } } }
