AtCoder ABC 379 D - Home Garden (2Q, 茶色, 400 点)

「全体に足す」のは難しいから、足す値を別途持っておくというスキル！！！　

• 問題へのリンク

問題概要

以下の 個のクエリに答えよ。

• クエリタイプ 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;
        }
    }
}