QOJ.ac

QOJ

Time Limit: 5 s Memory Limit: 256 MB Total points: 100
[+1]

# 3685. 序列操作

Statistics

问题描述

有一个长度为 n 的序列,有三个操作

  1. I a b c 表示将 [a,b] 这一段区间的元素集体增加 c
  2. R a b 表示将 [a,b] 区间内所有元素变成相反数,
  3. Q a b c 表示询问 [a,b] 这一段区间中选择 c 个数相乘的所有方案的和 mod 的值。

输入格式

第一行两个数 nq 表示序列长度和操作个数。

第二行 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 10q \leq 10

30\% 的数据没有 IR 操作。

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)