F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:祝各位Oier新年快乐,Rp++!
Problem 2962. -- 序列操作

2962: 序列操作

Time Limit: 50 Sec  Memory Limit: 256 MB
Submit: 1156  Solved: 381
[Submit][Status][Discuss]

Description

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

Input

  第一行两个数n,q表示序列长度和操作个数。
  第二行n个非负整数,表示序列。
  接下来q行每行输入一个操作I a b c或者 R a b或者Q a b c意义如题目描述。

Output

  对于每个询问,输出选出c个数相乘的所有方案的和mod19940417的值。

Sample Input

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

Sample Output

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。

HINT

  100%的数据n<=50000,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)。

Source

中国国家队清华集训 2012-2013 第三天

[Submit][Status][Discuss]

HOME Back