加减乘除
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
小 C 有一个长度为 的整数序列 ,他需要处理 次操作,包含两类:
-
操作 包含一个非负整数 和两个正整数 和 。对于所有大于或等于 的元素,需要先将其加上 ,然后再乘以 。也就是对于一个值为 且满足 的元素,在此操作后它变为 。
-
操作 包含一个非负整数 和两个正整数 和 。对于所有小于或等于 的元素,需要先将其减去 ,然后再除以 ,并向零截断。也就是对于一个值为 且满足 的元素,在此查询后它变为
- 其中, 表示向零截断 得到的整数。“向零截断”意味着将小数部分去掉,使结果接近零。例如,截断 得到 ,而截断 得到 。
在依次应用了 次操作之后,数组中有多少元素在 到 的范围内(也即满足 )?
输入格式
- 第一行包含四个整数 , , , 和 :表示数组的长度 ,查询次数 ,以及你需要统计的范围 。
- 第二行包含 个整数 :表示数组 的初始状态。
- 接下来的 行,每行包含四个整数 , , , 和 :表示第 次操作的类型和参数。
输出格式
- 在一行中输出一个整数,表示在处理完所有查询后,数组中有多少元素满足 。
测试样例
Input 1
3 3 3 10
1 -2 3
1 2 2 3
2 20 1 3
2 1 20 5
Output 1
1
Input 2
10 10 -344 949304959823841996
-3322545 4925407 1739804 2427239 -5261662 -5616033 -8030330 6212172 8586142 5029512
1 16392506 3 3
1 32437 46 3
1 27923410 74 5
1 579357460 33 5
2 2620867453 17 1
2 3538613740 16 1
1 3046695459 20 3
1 2820482772 12 2
1 3554938917 20 5
2 91948363102 2 1
Output 2
6
数据范围与约束
对于全部测试数据,满足 $ 1 \leq n,Q \leq 2 \times 10^5,\, -2^{63} < L \leq R < 2^{63},\,0 \leq |A_i| \leq 10^9 ,\, q_i \in \{1, 2\} ,\, 0 \leq x_i < 2^{63} ,\,1 \leq s_i, t_i \leq 10^9 $,并且在处理查询的过程中,数组中任何元素的绝对值不会超过 。
- 对于 的测试数据,满足
- 另有 的测试数据,满足