TouchStone
  Please Login
Login Sign Up
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4875
  • Problem
  • P4875前缀前缀和
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 1s,512m
    Description

    有一个长度为n的整数数列A1,A2,...,An。
    我们定义前缀和 Sum[i]=A1+A2+...+Ai
    我们定义前缀前缀和 SSum[i]=Sum[1]+Sum[2]+...+Sum[i]

    现在进行了m次操作,操作有下面两种:

    1. Modify i d 将Ai的值改为d;

    2. Query i 询问SSum[i]的值

    对于每次询问,你需要做出快速回答

    Input Format

    第一行有两个整数N和M

    第二行,n个整数,表示初始序列A1,A2….An。

    接下来m行,每行表示一次操作

    Output Format

    对于每个询问,输出一行,一个整数,表示询问的答案

    Sample Input 1

    5 3
    1 2 3 4 5
    Query 5
    Modify 3 2
    Query 5

    Sample Output 1

    35
    32

    Sample Input 2

    10 5
    11 45 51 77 32 89 81 90 93 73
    Query 9
    Query 1
    Query 6
    Modify 7 9
    Query 3

    Sample Output 2

    2310
    11
    879
    174

    Sample Input 3

    10 10
    78 79 49 77 96 63 21 61 1 61
    Query 1
    Modify 7 95
    Query 3
    Query 3
    Modify 5 26
    Query 7
    Query 5
    Modify 9 26
    Query 3
    Modify 1 69

    Sample Output 3

    78
    441
    441
    1872
    1033
    441

    Hint

    对于100%的数据:
    1<=N,M<=100000
    0<=Ai<=100000
    不管如何修改,Ai的值始终在上述范围内