TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P4875
  • 题目
  • P4875前缀前缀和
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,512m
    问题描述

    有一个长度为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]的值

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

    输入格式

    第一行有两个整数N和M

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

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

    输出格式

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

    样例输入 1

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

    样例输出 1

    35
    32

    样例输入 2

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

    样例输出 2

    2310
    11
    879
    174

    样例输入 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

    样例输出 3

    78
    441
    441
    1872
    1033
    441

    提示

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