#D. 希蒙的玩具兵团

    传统题 1000ms 256MiB

希蒙的玩具兵团

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

希蒙下达命令让nn个士兵们站成一行。不妨认为它们站在了一个数轴上,每个士兵的位置就是它脚下数轴的数字。希蒙会告诉你,第 ii 个士兵的位置为 aia_i不保证 aia_i升序

数轴的长度是有限制的,具体的范围是 [k,k][-k,k]。也就是说,如果某个士兵移出了这个范围,它就脱离了这个队列了,并且不会再次回到队列当中。

为了训练士兵,希蒙给士兵们下达了 mm 个指令,有以下 3 种:

指令 1:全体士兵向数轴的正方向移动 xx 个单位长度。

指令 2:全体士兵往数轴的反方向移动 xx 个单位长度。

指令 3:依次报数,统计目前队列里一共有多少个士兵。

但是希蒙发现,士兵兵团的大小实在是太大了,以至于执行这些操作变得非常缓慢。尽管如此,希蒙仍然希望你告诉他所有指令 3 的结果。

输入格式

第一行共有 33 个整数 n,m,kn, m, k,含义如题面所示。

第二行共有 nn 个整数 a1,a2,,ana_1, a_2, \cdots, a_n,表示每个士兵的位置。

接下来 mm 行,有 11 或者 22 个正整数,描述一条指令。首先是一个整数 op\operatorname{op},表示这条指令的类型。如果 1op21 \leq \operatorname{op} \leq 2,接下来还会输入一个整数 xx

输出格式

对于每条指令 3 ,输出一个整数,表示目前还在队列中的士兵的数目。

样例

输入样例

3 4 3
-1 1 2
2 3
3
1 5
3

输出样例

2
1

数据范围与提示

样例 1 说明 一共有三个士兵。初始时,它们的站位分别是 [1,1,2][-1,1,2]

第一次操作后,所有士兵向左移动 33 格,位置变成了 [[4-4,2,1],-2,-1]。第一个士兵被移出了数轴。

第二次操作后,输出当前的士兵数目,为 22 个。

第三次操作后,所有士兵向右移动 55 格,位置变成了 [3,[3,44]],第二个士兵被移出了数轴。

第四次操作后,输出当前的士兵数目,为 11 个。

数据规模与约定 对于 30%30\% 的数据,1n,m5×1031 \leq n, m \leq 5\times 10^3; 对于另外 20%20\% 的数据,1k5001\le k\le 500; 对于 100%100\% 的数据,1n,m3×1051 \leq n, m \leq 3\times 10^51k,x2×1091 \leq k, x \leq 2 \times 10^9kaik-k \le a_i \le k

此题可能会需要手动模拟队列/双向队列,可参考下列链接双向队列

金牌集训营编程测试-2-20230716

未参加
状态
已结束
规则
IOI
题目
7
开始于
2023-7-16 18:30
结束于
2023-7-16 20:00
持续时间
1.5 小时
主持人
参赛人数
65