シミュレーションを用いてクエリを処理することを考えます。このとき、管理する必要のある情報は

• マス \(i\) \((1\leq i\leq N)\) に積まれているブロックの数 \(A_i\)
• \(j\) 個 \((1\leq j\leq Q)\) 個以上のブロックが積まれているマスの数 \(B_j\)

です。しかし、これらを管理しようとすると、すべてのマスから \(1\) 個ずつブロックを削除するたびに \(B_j\) をすべて更新する必要があり、最大で \(\Theta(Q^2)\) 回更新する必要があり、時間制限が厳しいです。

その点に向けた工夫はいくつか考えられますが、一例としてはそもそも「すべてのマスから \(1\) 個ずつブロックを削除する」操作を行わない、ということが考えられます。このとき、元の問題における \(2\) 種類目のクエリにおいて出力すべき値は、削除しない場合における以下の値と等しいです。

各マスに積まれているブロックの個数の最小値 \(\displaystyle\min_{1\leq i\leq N} A_i\) を \(k\)としたとき、\((y+k)\) 個以上のブロックが積まれているマスの個数 \(B_{y+k}\)

ここで、クエリごとに \(\displaystyle\min_{1\leq i\leq N} A_i\) を求めると最悪の場合、全体で \(O(NQ)\) の時間計算量がかかってしまいますが、この値は \(B_j=N\) である最大の \(j\) と言い換えることもできます。 この値は \(1\) 種類目のクエリのたびに高々 \(1\) 増加するかどうかであるため、この値をシミュレーションを通じて管理し続け、クエリのたびに更新されたかを確認することで全体で \(O(Q)\) の計算量で処理することができます。

以上を踏まえると、\((A_1,\ldots,A_N)\), \((B_1,\ldots,B_Q)\), \(k\) を保持して以下のようにクエリを処理することができます。

• 最初の状態

  • \(A_i=0\)
  • \(B_j=0\)
  • \(k=0\)

• \(1\) 種類目のクエリ

  • \(A_x\) を \(1\) 増やす。
  • \(B_{A_x}\) を \(1\) 増やす。
  • \(B_{A_x}=N\) ならば \(k=N\) に変更する。

• \(2\) 種類目のクエリ

  • \(k+y>Q\) ならば \(0\), \(k+y\leq Q\) ならば \(B_{k+y}\) を出力する。

必要な計算量は \(O(N+Q)\) となり、十分高速です。よって、この問題を解くことができました。

C++ による実装例:

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

#define N (int)3e+5

int main(void){
	int a[N+1]={};
	int c[N+1]={};
	int n,q,t,x,mn=0;

	cin>>n>>q;
	for(int i=0;i<q;i++){
		cin>>t>>x;
		if(t==1){
			a[x]++;
			c[a[x]]++;
			if(c[a[x]]==n)mn=a[x];
		}
		if(t==2){
			if(x+mn>q)cout<<0<<endl;
			else cout<<c[x+mn]<<endl;
		}
	}

	return 0;
}