QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB
Statistics

Bobo 精通数据结构!他想维护一个线段的集合 $S$。初始时,$S$ 为空。他会依次进行 $q$ 次操作,操作有 $2$ 种。

  • 类型 $1$:给出 $l, r$,向集合 $S$ 中插入线段 $[l, r]$.
  • 类型 $2$:给出 $l, r$,询问满足 $[x, y] \in S$ 且 $x \leq l \leq r \leq y$ 的线段 $[x, y]$ 数量。

帮 Bobo 求出每次询问的答案。

输入格式

输入文件包含多组数据,请处理到文件结束。

每组数据的第一行包含 $2$ 个整数 $n$ 和 $q$. 其中 $n$ 表示操作中 $r$ 的最大值。

接下来 $q$ 行中的第 $i$ 行包含 $3$ 个整数 $t_i, l_i, r_i$,表示第 $i$ 个操作属于类型 $t_i$,对应的参数是 $l_i$ 和 $r_i$.

输出格式

对于每个类型 $2$ 的询问,输出 $1$ 个整数表示对应的数量。

样例输入

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

样例输出

1
1
2

数据范围

  • $1 \leq n, q \leq 10^5$
  • $t_i \in \{1, 2\}$
  • $1 \leq l_i \leq r_i \leq n$
  • 对于 $t_i = 2$ 的操作,$r_i - l_i \leq 2$ 成立。
  • 数据组数不超过 $10$.