QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100
Statistics

时间限制1s,空间限制256MB

后面有简要版题意

有个卖瓜摊子,这个摊子有 $m$ 个瓜,编号为 $1$ 至 $m$。接下来依次发生 $n$ 个事件,每次是以下两种事件之一:

  • 1 l r 满足 $1\leqslant l \leqslant r \leqslant m$:表示来了一个学姐,想要购买编号位于 $[l,r]$ 中的瓜。如果要满足这个学姐就必须把 $[l,r]$ 的瓜全给她
  • 2 l r 满足 $1\leqslant l \leqslant r \leqslant m$:表示学姐们对卖瓜老板的一次询问。遵循一瓜最多一姐的原则,且只能出售编号位于 $[l,r]$ 中的瓜,询问当前最多能满足多少个学姐的要求。由于学姐们纯粹是故意找茬,所以她们只是询问但不会真的买瓜,询问之间互相独立

卖瓜老板如果答错或答不出来,学姐们就会觉得卖瓜老板挺能藏的,而这个后果是十分严重的!

现在,作为卖瓜老板的好友刘华强,请你帮帮他。

简要版题意:$n$ 次操作,每次操作如下:

  • 1 l r:加入区间 $[l,r]$,满足 $1\leqslant l \leqslant r \leqslant m$.
  • 2 l r:询问区间 $[l,r]$,满足 $1\leqslant l \leqslant r \leqslant m$,询问最大不相交区间数,且选出的区间都位于 $[l,r]$ 中。

我们称一个区间 $[l_1,r_1]$ 位于 $[l_2,r_2]$ 中当且仅当 $l_2\leqslant l_1 \leqslant r_1 \leqslant r_2$.

输入格式

第一行两个整数 $n,m$.

接下来 $n$ 行,每行三个整数 $opt,l,r$.

输出格式

对于每个2操作,输出一行一个整数。

样例一

input

16 16
2 3 4
1 3 7
2 1 3
2 1 16
1 1 5
1 9 10
2 5 16
1 2 6
2 5 13
1 11 12
2 7 11
2 4 9
1 13 14
1 15 16
1 4 8
2 4 13

output

0
0
1
1
1
1
0
3

样例二

input

16 16
1 2 4
2 3 10
1 13 15
1 7 9
1 3 5
2 1 16
2 3 8
2 1 13
1 8 10
2 8 8
2 6 9
2 6 16
1 5 7
2 3 3
1 8 10
2 8 8

output

0
3
1
2
0
1
2
0
0

对于 $20\%$ 的数据,满足 $n,m\leqslant 2*10^3$.

对于 $50\%$ 的数据,满足 $n,m\leqslant 8*10^4$.

对于 $100\%$ 的数据, 满足 $n,m\leqslant 3*10^5,1\leqslant opt \leqslant 2$.