A2573. 序列操作
编程题
提高+/省选-
知识点
题目描述
**滥用评测功能将被封号。**有一个长度为 $n$ 的序列，有三个操作：
1.
2.
3.
1.
I a b c 表示将 $[a,b]$ 这一段区间的元素集体增加 $c$；2.
R a b表示将 $[a,b]$ 区间内所有元素变成相反数；3.
Q a b c 表示询问 $[a,b]$ 这一段区间中选择 $c$ 个数相乘的所有方案的和 $\mod 19940417$ 的值。输入格式
第一行两个数 $n, q$ 表示序列长度和操作个数。
第二行 $n$ 个整数，表示序列。
接下来 $q$ 行每行输入一个操作
第二行 $n$ 个整数，表示序列。
接下来 $q$ 行每行输入一个操作
I a b c 或者 R a b 或者 Q a b c，意义如题目描述。输出格式
对于每个询问，输出选出 $c$ 个数相乘的所有方案的和 $\mod 19940417$ 的值。
输入输出样例
输入 #1
5 5 1 2 3 4 5 I 2 3 1 Q 2 4 2 R 1 5 I 1 3 -1 Q 1 5 1
输出 #1
40 19940397
说明/提示
**样例说明：**
做完第一个操作序列变为
第一次询问结果为 $3 \times 4+3 \times 4+4 \times 4=40$。
做完
做完
第二次询问结果为 $-2-4-5-4-5=-20$。
**数据范围：**
对于 $100\%$ 的数据，$n \leq 50000, q \leq 50000$。初始序列的元素的绝对值 $\leq 10^9$，保证 $[a,b]$ 是一个合法区间，
做完第一个操作序列变为
1 3 4 4 5。第一次询问结果为 $3 \times 4+3 \times 4+4 \times 4=40$。
做完
R 操作变成 -1 -3 -4 -4 -5。做完
I 操作变为 -2 -4 -5 -4 -5。第二次询问结果为 $-2-4-5-4-5=-20$。
**数据范围：**
对于 $100\%$ 的数据，$n \leq 50000, q \leq 50000$。初始序列的元素的绝对值 $\leq 10^9$，保证 $[a,b]$ 是一个合法区间，
I 操作中 $|c| \leq 10^9$，Q 操作中 $1 \leq c \leq \min(b-a+1,20)$。