本文共 2874 字，大约阅读时间需要 9 分钟。

Ryuji is not a good student, and he doesn't want to study. But there are n books he should learn, each book has its knowledge a[i]a[i]a[i].

Unfortunately, the longer he learns, the fewer he gets.

That means, if he reads books from lll to rrr, he will get a[l]×L+a[l+1]×(L−1)+⋯+a[r−1]×2+a[r]a[l] \times L + a[l+1] \times (L-1) + \cdots + a[r-1] \times 2 + a[r]a[l]×L+a[l+1]×(L−1)+⋯+a[r−1]×2+a[r] (LLL is the length of [ lll, rrr ] that equals to r−l+1r - l + 1r−l+1).

Now Ryuji has qqq questions, you should answer him:

111. If the question type is 111, you should answer how much knowledge he will get after he reads books [ lll, rrr ].

222. If the question type is 222, Ryuji will change the ith book's knowledge to a new value.

Input

First line contains two integers nnn and qqq (nnn, q≤100000q \le 100000q≤100000).

The next line contains n integers represent a[i](a[i]≤1e9)a[i]( a[i] \le 1e9)a[i](a[i]≤1e9) .

Then in next qqq line each line contains three integers aaa, bbb, ccc, if a=1a = 1a=1, it means question type is 111, and bbb, ccc represents [ lll , rrr ]. if a=2a = 2a=2 , it means question type is 222 , and bbb, ccc means Ryuji changes the bth book' knowledge to ccc

Output

For each question, output one line with one integer represent the answer.

样例输入复制

5 31 2 3 4 51 1 32 5 01 4 5

样例输出复制

108

题目来源

将a[i]*(r-i+1)化成a[i]*(r+1)-a[i] 然后建两个二叉树， 一个维护区间和， 一个维护前缀区间和。

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;const int maxn=100005;long long int a[maxn];long long int t1[maxn<<2];long long int t2[maxn<<2];int n,q;void pushup (int re,long long int* t){    t[re]=t[re<<1]+t[re<<1|1];}void build1 (int l,int r,int re,long long int* t){    if(l==r)    {        t[re]=a[l];        return;    }    int mid=(l+r)>>1;    build1 (l,mid,re<<1,t);    build1 (mid+1,r,re<<1|1,t);    pushup (re,t);}void build2 (int l,int r,int re,long long int* t){    if(l==r)    {        t[re]=a[l]*l;        return;    }    int mid=(l+r)>>1;    build2 (l,mid,re<<1,t);    build2 (mid+1,r,re<<1|1,t);    pushup (re,t);}void update1 (int l,int r,int re,int loc,long long int data,long long int* t){    if(l==r)    {        t[re]=data;        return;    }    int mid=(l+r)>>1;    if(mid>=loc)        update1 (l,mid,re<<1,loc,data,t);    else        update1 (mid+1,r,re<<1|1,loc,data,t);    pushup(re,t);}void update2 (int l,int r,int re,int loc,long long int data,long long int* t){    if(l==r)    {        t[re]=data*l;        return;    }    int mid=(l+r)>>1;    if(mid>=loc)        update2 (l,mid,re<<1,loc,data,t);    else        update2 (mid+1,r,re<<1|1,loc,data,t);    pushup(re,t);}long long int query (int l,int r,int re,int left,int right,long long int* t){     if(l>=left&&r<=right)        return t[re];     long long int ans=0;     int mid=(l+r)>>1;     if(mid>=left)        ans+=query (l,mid,re<<1,left,right,t);     if(mid
      
     
    
   

转载地址：http://ytaen.baihongyu.com/