#1774. 序列操作
序列操作
序列操作
题目描述
标题: 序列操作 - Problem - QOJ.ac
#3685. 序列操作
The problem was used in the following contests:
问题描述
有一个长度为 n 的序列,有三个操作
I a b c表示将 [a,b] 这一段区间的元素集体增加 c,R a b表示将 [a,b] 区间内所有元素变成相反数,Q a b c表示询问 [a,b] 这一段区间中选择 c 个数相乘的所有方案的和 mod19940417 的值。
输入格式
第一行两个数 n,q 表示序列长度和操作个数。
第二行 n 个非负整数,表示序列。
接下来 q 行每行输入一个操作 I a b c 或者 R a b 或者 Q a b c 意义如题目描述。
输出格式
对于每个询问,输出选出 c 个数相乘的所有方案的和 mod19940417 的值。
样例输入
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×4+3×4+4×4=40。
做完 R 操作变成 -1 -3 -4 -4 -5。
做完 I 操作变为 -2 -4 -5 -4 -5。
第二次询问结果为 −2−4−5−4−5=−20。
数据规模和约定
10% 的数据 n≤10,q≤10。
另 30% 的数据没有 I 和 R 操作。
另 30% 的数据没有 I 操作。
100% 的数据:
- 1≤n≤50000
- 1≤q≤50000
- 初始序列的元素的绝对值 ≤109。
I a b c中保证 [a,b] 是一个合法区间,|c|≤109。R a b保证 [a,b] 是个合法的区间。Q a b c中保证 [a,b] 是个合法的区间 1≤c≤min(b−a+1,20)。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 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
40
19940397