簡単な解法として、愚直に植物とその高さを管理する方法が考えられます。ですが、この場合では時間計算量が \(O(Q^2)\) となり、高速ではありません。この愚直に管理する時のボトルネックになるのが全ての植物の高さを \(H\) 増加させる \(2\) 種類目のクエリです。

植物に関する情報を適切に管理することでこの \(2\) 種類目のクエリの処理を高速にすることを考えます。

まず、操作の特徴について考えると、植物は常に先に操作されたクエリの時に植えられた植物であればあるほど高さが高いということがわかります。そして、\(A_i =\)( 最初に植物が植えられて、それが収穫されずに\(i\) 番目のクエリまで処理された場合の高さ) とすると、 \(i\) 番目のクエリで植えられた植物の \(j(>i)\) 番目のクエリを行う前の高さは \(A_{j-1}-A_i\) であることが言えます。

つまり、ある時点でのある植物の高さを求めるにはそれが植えられたのが何番目のクエリかがわかれば十分です。よって、\(2\) 種類目のクエリではすべての植物に対して高さを更新する必要がありません。 そして、この \(A\) はクエリを処理すると同時に計算することができます。 \(i\) 番目のクエリが \(2\) 種類目であるときは、\(A_i=A_{i-1}+T\) となり、それ以外の場合は \(A_i=A_{i-1}\) です。

最後に、実際にどのように \(1,3\) 種類目のクエリを処理するかを考えます。 先ほど述べたように、植物を高さで管理するのではなく、植えたのが何番目のクエリかで管理します。また植えられた順序で並べられてると良いため、キュー というデータ構造が有効です。\(1\) 種類目のクエリは追加する操作で、そのクエリの番号をキューに追加します。 \(3\) 種類目のクエリは、植物が植えられたクエリの番号が小さい順に植物を見ていき、求めた \(A\) を用いて高さを計算して植物の高さが \(H\) 以上である場合は収穫し、そうでなければ収穫することをやめるという処理を行うことで答えを求めることができます。各植物は植えられたら \(1\) 回しか収穫されないため、全クエリを通して最大で \(Q\) 回までしか合計で収穫されません。また、実際に収穫しない植物を確認する回数は \(3\) 種類目のクエリ \(1\) 回につき高々 \(1\) 回であるため最大で \(Q\) 回です。よって、全体で \(O(Q)\) でクエリを処理できます。

実装する際はオーバーフローなどに気をつけてください。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin >> q;
    queue<int> que;
    vector<long long> height(q + 1);
    height[0] = 0;
    for (int i = 0; i < q; ++i) {
        int t;
        cin >> t;
        if (t == 1) {
            height[i + 1] = height[i];
            que.push(i);
        }
        if (t == 2) {
            long long add;
            cin >> add;
            height[i + 1] = height[i] + add;
        }
        if (t == 3) {
            height[i + 1] = height[i];
            long long h;
            cin >> h;
            int ans = 0;
            while (!que.empty()) {
                if (height[i + 1] - height[que.front()] >= h) {
                    ans++;
                    que.pop();
                } else {
                    break;
                }
            }
            cout << ans << "\n";
        }
    }
}