CF74D Hanger

在一家非常大且知名的公司中，有一间衣帽间，里面有一个挂衣架。挂衣架上有 $ n $ 个钩子，排成一行，从左到右依次编号为 1 到 $ n $。 公司员工的工作时间安排十分复杂。当一天工作开始时，所有员工都不在公司，挂衣架是空的。在某些时刻，会有员工到来或离开。 当某位员工到来时，他会将外套挂在一个可用的钩子上。为了尽量减少对同事的打扰，选择挂外套的钩子是有原则的：首先，员工选择一段连续的可用钩子中最长的一段。如果有多个这样的段，则选最靠右的。然后将外套挂在这段的中间位置。如果段中有偶数个钩子，则选择两个中间钩子中较靠右的一个。 当一个员工离开时，他会取下自己的外套。由于公司员工互相尊重，没有人会拿错外套。 公司老板有时会感到无聊，就会指派秘书去查看某段钩子（从第 $ i $ 个到第 $ j $ 个，包括这两个钩子）上挂着多少件外套。如果不满足老板的这个要求，他会发火并情绪崩溃。 为了减少在老板办公室和衣帽间之间来回奔波的时间，秘书请求你编写一个程序来模拟公司的衣帽间工作情况。

第一行包含两个整数 $ n $ 和 $ q $，分别表示挂衣架上的钩子总数和请求总数。满足条件为 $ 1 \le n \le 10^9 $ 和 $ 1 \le q \le 10^5 $。接下来的 $ q $ 行按时间顺序排列着请求。类型为 " $ 0 $ $ i $ $ j $ "（其中 $ 1 \le i \le j \le n $）的是老板的请求。输入至少包含一个老板的请求。其他情况下，输入中包含一个不超过 $ 10^9 $ 的正整数，表示员工的标识符。一个员工标识符在请求列表中出现的奇数次表示他到达，偶数次表示他离开。所有员工的标识符都是唯一的。每当有员工到来时，总有一个空闲的钩子可供使用。

对于输入中的每一个老板请求，输出一行，表示从第 $ i $ 个钩子到第 $ j $ 个钩子（包括这两个钩子）之间所挂外套的数量。 **本翻译由 AI 自动生成**