UOJ Logo Zijian Online Judge

ZOJ

#55. 石子移动

统计

题目描述

有 $n$ 颗石子排成一行,第 $i$ 颗石子初始位置为 $a_i$ 。

fpdqwq 对这些石子进行了 $q$ 次操作,第 $i$ 次操作将所有满足 $\mod x_i = y_i$ 的位置 $p$ 上所有石子向 $z_i$ 方向移一个位置

($z_i=1$表示向正方向移动,$z_i=-1$表示向负方向移动)

进行完操作后,fpdqwq也不知道石子都被移动到哪里去了,于是向你询问位置范围 $[l,r]$ 中(即位置$l,l+1,...,r$)还剩多少石子

输入格式

第一行两个正整数 $n, q$ ,用空格分隔,分别代表石子数和操作次数

第二行 $n$ 个整数 $a_1, a_2, ..., a_n$ ,代表所有石子的初始位置

接下来 $q$ 行每行 $3$ 个整数 $x_i, y_i, z_i$ ,代表一次操作

最后一行两个正整数 $l,r$ ,代表被询问的区间

输出格式

一行一个整数代表答案

样例输入

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

样例输出

3

样例解释

第一次操作移动了所有石子,第二次操作移动了第 $2,4$ 颗石子,最后一次操作石没有移动任何石子,最终第 $1,3,5$ 颗石子位于 $[0,5]$ 内

数据范围与约定

对于$24\%$的数据:$n \leq 100, q \leq 100$

对于$60\%$的数据:$n \leq 5000, q \leq 5000$

对于$97\%$的数据:$n \leq 100000, q \leq 100000$

对于$100\%$的数据:$1 \leq n \leq 500000, 0 \leq q \leq 500000, 0 \leq a_i \leq 10^9, 0 \leq y_i < x_i \leq 10^9, 0 \leq l \leq r \leq 10^9, |z_i|=1$

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$