#2018. 学姐买瓜

    ID: 2018 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest754来源:qoj.ac数据:公开样例线段树

学姐买瓜

学姐买瓜

题目描述

标题: 学姐买瓜 - Problem - QOJ.ac

#4894. 学姐买瓜

Statistics

The problem was used in the following contests:

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

后面有简要版题意。

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

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

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

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

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

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

我们称一个区间 [l1,r1] 位于 [l2,r2] 中当且仅当 l2⩽l1⩽r1⩽r2.

输入格式

第一行两个整数 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⩽2∗103.

对于 50% 的数据,满足 n,m⩽8∗104.

对于 100% 的数据, 满足 n,m⩽3∗105,1⩽opt⩽2.

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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
0
0
1
1
1
1
0
3

样例 2

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
0
3
1
2
0
1
2
0
0