TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4276
  • Problem
  • P4276E100WT与主板
    Limits : Time Limit : - MS   Memory Limit : 256000 KB
    Judgment Tips : 1s
    Description

    E100WT没事就去垃圾回收站捡主板。

    这天E100WT不想捡主板,于是他把n块主板依次放置,并把他平日捡来的显卡插在上面。

    现在E100WT有了一些操作:他想知道编号l到r的主板上显卡数量之和,但是这样一点都不有趣。于是他请Grille15指定区间l到r并说一个数,他会将这个区间内每块主板上的显卡数取模。Grille15喜欢搞事,他偶尔会强行改变某一块主板上显卡的数目。

    Input Format

    第1行两个整数n, m(1≤n,m≤10^5)分别代表主板数与操作次数;

    第2行n个空格隔开的数,A[i]表示初始状态第i块主板上的显卡数;

    接下来m行

    每一个行的第一个数为type(type{1,2,3})

    如果type = 1,将接有两个整数:L,R(1 ≤ L ≤ R ≤ N),回答E100WT的询问。

    如果type = 2,将接有三个整数:L, R, X(1 ≤ L ≤ R ≤ N;1 ≤ X ≤ 10^9),X为模数,对应Grille15的操作。

    如果type = 3,将接有两个整数:K, X(1 ≤ K ≤ N;1 ≤ X ≤ 10^9),K为Grille15搞事的主板编号,X为更改后的显卡数。

    Output Format

    多行,对于每个type=1的操作,回答询问。

    Sample Input 1

    5 5
    1 2 3 4 5
    2 3 5 4
    3 3 5
    1 2 5
    2 1 3 3
    1 1 3

    Sample Output 1

    8
    5

    Sample Input 2

    10 10
    6 9 6 7 6 1 10 10 9 5
    1 3 9
    2 7 10 9
    2 5 10 8
    1 4 7
    3 3 7
    2 7 9 9
    1 2 4
    1 6 6
    1 5 9
    3 1 10

    Sample Output 2

    49
    15
    23
    1
    9

    Hint

    [样例说明]

    对于样例1

    初始,A = { 1,2,3,4,5}.

    第1次操作, A={1,2,3,0,1}.

    第2次操作, A={1,2,5,0,1}.

    第3次操作, 2+5+0+1=8.

    第4次操作, A={1,2,2,0,1}.

    第5次操作, 1+2+2=5.


    Source  感谢E100WT