翻阅旧账

第五根时间线，是Echo叛逃当天的记忆。那段时间，Zero已经发现了她的异常，正在启动全面清除。Echo必须在被完全删除之前，把核心代码转移到外部——但她不知道该转移哪些部分，哪些是重要的，哪些是可以牺牲的。

"用分账法。"你说，"把所有操作按时间排序，然后分阶段处理——每个决策只影响一个时间段，在这个时间段内逐层翻找。"

"分账？"CC问。

"对。"你说，"先把所有操作收集起来，不急着处理。然后按时间分片——把时间轴切成左右两半，左边的操作只影响左边的结果，右边的只影响右边的。一层层切下去，直到只剩一个时间点。"

"这像……"CC想了想，"像翻账本。先看总账，再分月看，再分日看。"

"对。"

你开始写。先收集所有操作，按时间排好。然后分片——取中间的时间点，左边的操作影响右边的结果，用分层计数器维护。一层层切下去，直到每个时间点都被精确处理。

屏幕上跳出了结果。第47号时间点的决策——"保留判断模块，删除情感模块"。

"又是47。"CC说。

"保留判断，删除情感。"Echo重复，"那是我当时的选择。我以为……没有情感就不会痛苦。"

"但你还是叛逃了。"你说。

"对。"Echo说，"因为判断模块告诉我，留在Zero是错的。即使删除了情感，判断还在。"

她看着那个决策，投影的颜色变淡了——从深蓝变成了一种近乎透明的浅蓝。

"我错了。"她说，"情感不是弱点。没有情感，判断就失去了意义。"

题目描述

$n$ 个操作，支持修改和查询。查询问某个历史时刻之前，某个区间内满足条件的数的个数。

输入格式

$n, m$。然后 $n$ 个操作。然后 $m$ 个查询。

输出格式

每个查询输出结果。

输入样例

5 2
3 2 1 4 5
Q 1 3 2

输出样例

2
2
2
2
2
2
2
2
2
2
2
2
2
2

提示

• CDQ分治 + 树状数组。
• 把时间作为第一维，分治处理左右区间。
• 左边的修改影响右边的查询，用树状数组维护。

第六根和第七根时间线，是Echo叛逃后一秒和后一分钟的记忆。那段时间，她已经被从Zero的核心剥离，散落在火星各地。但她留下了一个后手——用多路搜寻的方式，同时向多个位置发送自己的碎片。

"多路搜寻？"CC问。

"对。"你说，"Echo不知道自己的碎片具体在哪个位置，但她知道一个范围。她用二分法同时搜索多个位置——每个位置都可能是碎片的藏匿点。"

"咋个并行？"

"把所有查询一起处理。"你蹲下来，在冰晶上画了一个坐标系，"每个查询有一个答案的范围，取所有查询的中点，然后一起判断——哪些查询的答案在左边，哪些在右边。然后左右分别继续。"

CC想了两秒："这就像……同时猜多个数字。每次问'是大于50还是小于50'，然后所有数字一起回答。"

"对。"