#534. D. 魔法

D. 魔法

题目描述

给定一个初始为空的可重集,你需要维护 QQ 次操作,每次操作形如:

  • 1 x:加入一个数 xx,保证 1≤x≤n1 \le x \le n。
  • 2 l r:询问区间 [l,r][l,r],对于所有 d∈[l,r]d \in [l,r],不断释放如下法术:
    • 将集合中所有数减去 dd,如果存在至少一个数 ≤0\le 0,则删除这些数后重新释放法术;否则结束释放。
    • 你需要求出总共 r−l+1r-l+1 个 dd 的释放次数之和。

输入格式

第一行两个整数 n,Qn,Q。

接下来 QQ 行,每行表示一个操作。

输出格式

对于每个 22 操作,输出一行一个整数表示答案。

样例

样例输入

10 10
2 7 9
1 6
2 7 10
1 10
1 7
2 7 10
1 7
1 1
2 6 7
1 4

样例输出

3
8
11
6

数据范围与约定

对于所有数据,有:

  • 1≤n≤1051 \le n\le 10^5
  • 1≤x≤n1 \le x \le n
  • 1≤Q≤1061 \le Q \le 10^6
测试点编号 附加限制
1∼41 \sim 4 n,Q≤103n,Q \le 10^3
5∼85 \sim 8 l=rl=r
9∼149 \sim 14 22 操作都在 11 操作之后
15∼1815 \sim 18 Q≤105Q \le 10^5
19∼2519 \sim 25 无