UOJ Logo Zijian Online Judge

ZOJ

Statistics

EI 在 BJOI 前集训的时候听到了集合分块题,他非常弱(现在依然很弱),比别人的算法多一个 $\log$ ,他想到的解决方法只有将分块大小修改,从而把复杂度包在里面变成 $\Theta(n \sqrt{n\log n})$ ,而且见到一道修改过的题后,他又不会做了:

有 $n$ 个集合 $S_i$ ,初始为空,接下来进行 $q$ 组操作:

  1. 将第 $l$ 个集合到第 $r$ 个集合插入一个元素 $x$ 即对 $l \le i \le r$,$S_i \leftarrow S_i \cup \{x\}$。

  2. 询问第 $l$ 个集合到第 $r$ 个集合的交集大小,即 $$\left| \bigcap_{i = l}^r S_i \right|$$

输入格式

第一行输入整数 $n, q$

接下来输入 $q$ 行,每行第一个数 $op$ 为操作类型

对应的输入为 1 $l\ r\ x$ 或者 2 $l\ r$

输出格式

对于每个操作 2 即询问,输出一个整数且换行表示答案。

样例 1

input

3 4
1 1 2 2
1 2 3 1
2 1 2
2 2 2

output

1
2

解释

操作后的各个集合:$[\{2\},\{1,2\},\{1\}]$

所以对于第一个询问,$\{2\} \cap \{1, 2\} = \{2\}$

样例 2

input

2 3
1 1 1 1
1 2 2 1
2 1 2

output

1

限制与约定

$1\le n, q \le 3 \times 10^5$, $1\le x \le q$, $1 \le l \le r \le n$

Subtask 1 (12 pts.),$1\le n, q \le 500$,插入的元素数量 $|S| \le 10^5$

Subtask 2 (18 pts.),$1 \le n, q \le 5 \times 10^3$,插入的元素数量 $|S| \le 10^5$

Subtask 3 (20 pts.),$1\le n, q \le 10^5$,插入的元素数量 $|S| \le 10^5$

Subtask 4 (28 pts.),$1\le n, q \le 10^5$

Subtask 5 (22 pts.),$1 \le n, q \le 3 \times 10^5$

Subtask $+\infty$ (0 pts.),你需要统计对于该区间的每一个子区间的答案之和。

时间限制:$2\,\mathrm{s}$

空间限制:$512\,\mathrm{MB}$