P2826 LJJ的数学课

    • 35通过
    • 127提交
  • 题目提供者 eden
  • 评测方式 云端评测
  • 标签 高性能
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    题目描述(本题是提高组第二题难度+)

    题目描述

    LJJ又要开始上数学课啦!(T1,永恒不变的数学)

    LJJ的Teacher对上次的考试很不满意(其实是出题人对上次的分数那么高不满意啦),决定在出一道难(water)题。


    LJJ的Teacher给了LJJ一个数列,但这由于是LJJ的Teacher发明的,我们不称呼他为LJJ数列,而称他为Teacher数列。但是LJJ还停留在数数的阶段啊,所以不能太难。


    于是LJJ的Teacher随便给出了一个Teacher数列。

    Teacher会对这个数列进行两个操作:

    1:将其中的一个数加上s(s为整数)

    2:Teacher会给出left和right,让你求:

    a[left]*(right-left+1) + a[left+1]*(right-left)

    • ...... + a[right-1]*2 + a[right]*1 的值。

    LJJ的指头掰不过来了呀,就请您来完成啦~

    输入输出格式

    输入格式:

    第一行有2个数n,q,分别表示Teacher数列中数的个数以及操作次数。

    接下来的一行有n个数,第i个数表示a[i]。

    再接下来q行,每行三个数;第一个数是order。如果order=1,那么接下来两个数:x, s,即把a[x]加上s;如果order=2,那么接下来两个数:left, right,即求这一段区间ljj要求的答案。

    注意:Teacher数列中的数并不一定都是正数,但一定都是整数。

    输出格式:

    对于每一个询问(order=2)输出所求答案

    输入输出样例

    输入样例#1: 复制
    5 3
    2 4 1 3 5
    2 2 4
    1 2 3
    2 2 4
    输出样例#1: 复制
    17
    26

    说明

    数据范围

    n<=100000, q<=100000,保证答案不超过long long (int64) 范围,保证数据有梯度

    样例解释

    4*3+1*2+3*1=17

    7*3+1*2+3*1=26

    提示 1.如果看不懂题目,那么看这里:给你一段数列,有两种操作,单点修改和区间查询。查询left到right,返回的值是

    a[left]*(right-left+1)+a[left+1]*(right-left)+...+a[right]*1。

    2.从另一个角度去想问题,把区间答案划分开来,否则你会打得很累。

    3.题目中说是单点修改,而不是区间修改,有没有觉得简单得不可思议呢?

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。