电源插排
测试数据来自 system/1859
描述
小 M 的实验室有很多电源插排。这些插排的编号从 1 到 N,由左向右排成一排。
每天早晨,这些插排都是没有被使用的。每当一个学生来到实验室,他就将自己的笔记本电源插到某一个未被使用的插排上。实验室的同学们都很奇怪,他们完成这个过程是这样的:首先,他们找到还没有被使用的插排的最长区间。如果有多个区间长度相同,他们就选择最靠右的那个。然后将自己的电源插到该区间的中间。如果区间长度是偶数,他们同样选择靠右的那个。当一个同学离开实验室时,他会将自己的电源拔出来。数据保证每一个同学来到实验室时,至少有一个空的插排。
现在给你实验室同学的来到和离开事件,和一些询问。对于每一个询问,你需要计算在区间 [L,R] 已经有多少个插排被使用了。
格式
输入格式
第一行是两个整数 N 和 Q,表示插排数量和询问数量。接下来 Q 行,每一行以一个整数 K 开头,如果 K 为 0,接下来就是两个整数 L 和 R(1 ≤ L ≤ R ≤ N),表示一个询问。否则表示编号为 K 的学生到来或离开 (K ≤ 109)。K 的奇数次出现表示到来,偶数次出现表示离开。每个学生的编号都是唯一的。
输出格式
对于每一个询问,输出一个整数,表示询问区间内有多少个插排已经被使用了。
样例1
样例输入1
7 10
1
2
3
0 1 2
0 4 7
0 2 5
20
0 6 6
99
0 4 6
样例输出1
1
2
2
1
3
限制
对于 30% 的数据,N ≤ \(10^5\),Q ≤ \(10^3\)
对于 100% 的数据,N ≤ \(10^9\),Q ≤ \(10^5\)
来源
天津省选2014 day1
信息
- ID
- 1792
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者