Let us perform a simulation to process the queries. What we need to manage is:

• \(A_i\), the number of blocks stacked on cell \(i\) \((1\leq i\leq N)\); and
• \(B_j\), the number of cells with \(B_j\) or more blocks \((1\leq j\leq Q)\).

However, naively maintaining them requires updating all entries of \(B_j\) every time a block is removed from all cells, costing a total of \(\Theta(Q^2)\) updates at maximum; this is unlikely to fit in the execution time limit.

There are several possible improvements to deal with this issue. For example, one can skip performing “removing a block from all cells.” In that case, the value that must be printed for a type-\(2\) query in the original problem equals the following value for non-removing approach:

Let \(k\) be the minimum number of blocks stacked in a cell, \(\displaystyle\min_{1\leq i\leq N} A_i\). Then the value to be printed is the number of blocks with at least \((y+k)\) blocks, that is, \(B_{y+k}\).

Here, if we try to find \(\displaystyle\min_{1\leq i\leq N} A_i\) for every query, it will cost a total of \(O(NQ)\) time at worst; however, this value can be rephrased as the maximum \(j\) with \(B_j=N\). This value can change only when a type-\(1\) query is processed, which either increases by one or is unchanged. Thus one can maintain this value throughout the entire simulation and check if an update is needed on each query. This costs a total of \(O(Q)\) time.

Therefore, the queries can be processed as follows, while maintaining \((A_1,\ldots,A_N)\), \((B_1,\ldots,B_Q)\), and \(k\):

• Initial state

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

• Type-\(1\) query

  • Increase \(A_x\) by \(1\).
  • Increase \(B_{A_x}\) by \(1\).
  • If \(B_{A_x}=N\), set \(k=N\).

• Type-\(2\) query

  • Print \(0\) if \(k+y>Q\); print \(B_{k+y}\) if \(k+y\leq Q\).

The total complexity is \(O(N+Q)\), which is fast enough. Thus, the problem has been solved.

Sample code in 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;
}