问题描述
有一个长度为 n 的序列,有三个操作
I a b c
表示将 [a,b] 这一段区间的元素集体增加 c,R a b
表示将 [a,b] 区间内所有元素变成相反数,Q a b c
表示询问 [a,b] 这一段区间中选择 c 个数相乘的所有方案的和 mod 的值。
输入格式
第一行两个数 n,q 表示序列长度和操作个数。
第二行 n 个非负整数,表示序列。
接下来 q 行每行输入一个操作 I a b c
或者 R a b
或者 Q a b c
意义如题目描述。
输出格式
对于每个询问,输出选出 c 个数相乘的所有方案的和 \bmod 19\,940\,417 的值。
样例输入
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
样例输出
40
19940397
样例解释
做完第一个操作序列变为 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。
数据规模和约定
10\% 的数据 n\leq 10,q \leq 10。
另 30\% 的数据没有 I
和 R
操作。
另 30\% 的数据没有 I
操作。
100\% 的数据:
- 1 \leq n \leq 50\,000
- 1 \leq q \leq 50\,000
- 初始序列的元素的绝对值 \leq 10^9。
I a b c
中保证 [a,b] 是一个合法区间,|c| \leq 10^9。R a b
保证 [a,b] 是个合法的区间。Q a b c
中保证 [a,b] 是个合法的区间 1 \leq c \leq \min(b-a+1,20)。