← 返回题目列表

Codeforces · 74/D

D. 衣架

中文机器翻译题面 查看原题

在一家非常大且非常受人尊敬的公司里,有一个带衣架的衣帽间。它由 n 个排成一排的钩子表示。钩子从左到右用 1 到 n 的正整数编号。

公司员工的工作安排非常复杂。工作日开始时,所有员工都不在,衣帽间的衣架是空的。有时员工会到达,有些则会离开。

当某个员工到达时,他将斗篷挂在可用的挂钩之一上。为了尽可能减少同事的不适,挂外套的挂钩是这样选择的。首先,员工在连续的可用钩子中选择最长的一段。如果有多个这样的片段,那么他会选择最靠近右侧的一个。之后,将外套挂在位于该部分中间的挂钩上。如果该段有偶数个钩子,则在两个中心钩子中我们选择最靠近右侧的一个。

当员工离开时,他会拿走外套。由于公司所有员工都互相尊重,没有人会抢别人的风头。

这家受人尊敬的公司的董事有时会感到无聊,他会派他的秘书去看看衣架上从第 i 个挂钩到第 j 个挂钩(含)有多少件外套。而这个突发奇想总是要实现的,不然导演会生气,精神崩溃。

不要花太多时间从主任办公室到衣帽间再回来,秘书让你写一个程序,模仿公司衣帽间的工作。

输入

第一行包含两个整数n、q(1≤n≤109,1≤q≤105),分别是衣架上的挂钩数量和对应的请求数量。然后按照 q 行请求,按照时间排序。 “0 i j”类型的请求 (1 ≤ i ≤ j ≤ n) — 是导演的请求。输入数据具有至少一个导演的要求。在所有其他情况下,请求包含一个不超过 109 的正整数——员工标识符。请求列表中员工标识符的每次奇怪出现都是他的到来。每一个偶数都是他的离开。所有员工都有独特的标识符。当任何员工到达时,总是至少有一个免费的挂钩。

输出

对于输入数据中每个导演的要求,在一行上打印一个数字 - 从第 i 件到第 j 件(含)挂在挂钩上的外套数量。

示例

输入 #1

9 11
1
2
0 5 8
1
1
3
0 3 8
9
0 6 9
6
0 1 9

输出 #1

2
3
2
5