H - ta-da
問題文
ストーリー
Monoxerの管理機能には、学習者の記憶状況の閲覧や分析、クラスおよびスクールとよばれる単位での所属の管理、学習者とのコミュニケーションの機能など様々備わっています。そのうちのひとつにリアクション機能というものがあります。学習者の学習状況などに対して「いいね！」か「ファイト！」のスタンプまたはフリーコメントを送信でき、学習者のモチベーションを上げる手助けとなります。
畔柳先生のクラスには、$N$人の生徒がいます。$N$人の生徒にはそれぞれ$1$から$N$までの整数の出席番号が割り振られています。
それぞれの生徒には非負整数で表されるモチベーションという数値があります。最初、すべての生徒のモチベーションは$0$です。
$Q$個のイベントが発生するので、与えられた順に処理してください。イベントは以下の3種類です。
- イベント$1$:
1 L Rの形式で与えられる。出席番号が$L$以上$R$以下の生徒のモチベーションが$1$上がる。 - イベント$2$:
2 L Rの形式で与えられる。$i=L,L+1,\ldots,R$それぞれについて、出席番号$i$の生徒はその時点でのモチベーションに等しい数の問題を解く。 - イベント$3$:
3 jの形式で与えられる。出席番号が$j$の生徒がその時点までに解いた問題の数を出力する。
制約
- $1 \le N, Q \le 2 \times 10^5$
- $1 \le L \le R \le N$
- $1 \le j \le N$
入力
$N$ $Q$
$Query_1$
$Query_2$
$\vdots$
$Query_Q$
$1$ $L$ $R$
$2$ $L$ $R$
$3$ $j$
出力
イベント$3$のイベントの個数$q$として、$q$行出力してください。$i$行目には、$i$個目のイベント$3$に対する答えを出力してください。
5 10
1 2 4
2 3 5
1 2 3
1 2 2
2 2 3
3 1
3 2
3 3
3 4
3 5
0
3
3
1
0
最初、$A={0,0,0,0,0}$です。それまでに解いた問題数を$B={0,0,0,0,0}$とします。
$1$番目のイベントでは、出席番号$2,3,4$の生徒のモチベーションが$1$上がり、$A={0,1,1,1,0}$となります。
$2$番目のイベントでは、出席番号$3,4,5$の生徒がモチベーションの数だけ問題を解き、$B={0,0,1,1,0}$となります。
$3$番目のイベントでは、出席番号$2,3$の生徒のモチベーションが$1$上がり、$A={0,2,2,1,0}$となります。
$4$番目のイベントでは、出席番号$2$の生徒のモチベーションが$1$上がり、$A={0,3,2,1,0}$となります。
$5$番目のイベントでは、出席番号$2,3$の生徒がモチベーションの数だけ問題を解き、$B={0,3,3,1,0}$となります。