【题目描述】

给定一个数列，有如下两种操作：

1：将其中的一个数加上s（s为整数）

2：给定区间[l,r],求a_l* (r-l+1) + a_l-1*(r-l)+ ...... + a_r-1*2 + a₁*1的值。

即：

$\Large \sum_{i=l}^{r} a_i·(r-i+1)$

【输入格式】

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

接下来的一行有n个数，第i个数表示$a_i$。

再接下来q行，每行三个数；第一个数是order。如果order=1，那么接下来两个数：x, s，即把$a_x$加上s；如果order=2，那么接下来两个数：l, r，即求这一段区间源氏要求的答案。

【输出格式】

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

【样例输入】

5 3

2 4 1 3 5

2 2 4

1 2 3

2 2 4

【样例输出】

17

26

【提示】

不保证数列全为正数，但保证是整数。

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

【来源】

未知

 

维护a_l* (r-l+1) + a_l-1*(r-l)+ ...... + a_r-1*2 + a₁*1 这个序列 

我们可以发现 这个和前缀和序列很相似 

于是我们可以 考虑一下前缀和 

 

S10:  a₁₀₊a₉ + a₈ + a₇ + a₆ + a₅ + a₄ + a₃ + a₂ + a₁

S₉:            a₉ + a₈ + a₇ + a₆ + a₅ + a₄ + a₃ + a₂ + a₁

S₈:     　　　　a₈ + a₇ + a₆ + a₅ + a₄ + a₃ + a₂ + a₁

S₇:  　　　　　　　a₇ + a₆ + a₅ + a₄ + a₃ + a₂ + a₁

S₆:  　　　　　　　　    a₆ + a₅ + a₄ + a₃ + a₂ + a₁

S₅:  　　　　　　　　　　　 a₅ + a₄ + a₃ + a₂ + a₁

S₄:　　　　　　　　　　　　　　a₄ + a₃ + a₂ + a₁

S₃:　　　　　　　　　　　　　　　　a₃ + a₂ + a₁

S₂:　　　　　　　　　　　　　　　　　　 a₂ + a₁

S₁: 　　　　　　　　　　　　　　　　　　　　a₁

 

显然 要查询[6,10] 的话 需要S₆₊S₇+S₈+S₉+S₁₀-(S₅*5) //5为[6,10] 的区间长度

我们可以用线段树维护输入序列前缀和的区间和  

单点修改的话 就成了区间修改 

修改 从当前位置一直到n

 

1 #include 
      
        2 #include 
       
         3  4 typedef long long LL; 5  6 const int MAXN=100010; 7  8 int n,q; 9 10 LL a[MAXN];11 12 struct SgtmentTree {13     int l,r;14     int tag;15     LL sum;16 };17 SgtmentTree t[MAXN<<2];18 19 inline void read(int&x) {20     int f=1;register char c=getchar();21     for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar());22     for(;isdigit(c);x=x*10+c-48,c=getchar());23     x=x*f;24 }25 26 inline void down(int now) {27     t[now<<1].tag+=t[now].tag;28     t[now<<1|1].tag+=t[now].tag;29     t[now<<1].sum+=(t[now<<1].r-t[now].l+1)*t[now].tag;30     t[now<<1|1].sum+=(t[now<<1|1].r-t[now<<1|1].l+1)*t[now].tag;31     t[now].tag=0;32 }33 34 void build_tree(int now,int l,int r) {35     t[now].l=l;t[now].r=r;36     if(l==r) {37         t[now].sum=a[l];38         return;39     }40     int mid=(l+r)>>1;41     build_tree(now<<1,l,mid);42     build_tree(now<<1|1,mid+1,r);43     t[now].sum=t[now<<1].sum+t[now<<1|1].sum;44 }45 46 void modify(int now,int l,int r,int v) {47     if(l<=t[now].l&&r>=t[now].r) {48         t[now].sum+=(LL)(t[now].r-t[now].l+1)*v;49         t[now].tag+=v;50         return;51     }52     if(t[now].tag) down(now);53     int mid=(t[now].l+t[now].r)>>1;54     if(l<=mid) modify(now<<1,l,r,v);55     if(r>mid) modify(now<<1|1,l,r,v);56     t[now].sum=t[now<<1].sum+t[now<<1|1].sum;57 }58 59 LL query(int now,int l,int r) {60     if(l<=t[now].l&&r>=t[now].r) return t[now].sum;61     LL ans=0;62     if(t[now].tag) down(now);63     int mid=(t[now].l+t[now].r)>>1;64     if(l<=mid) ans+=query(now<<1,l,r);65     if(r>mid) ans+=query(now<<1|1,l,r);66     return ans;67 }68 69 int hh() {70     freopen("overwatch.in","r",stdin);71     freopen("overwatch.out","w",stdout);72     read(n);read(q);73     for(int x,i=1;i<=n;++i) read(x),a[i]+=a[i-1]+x;74     build_tree(1,1,n);75     for(int type,x,y,i=1;i<=q;++i) {76         read(type);read(x);read(y);77         if(type==1) modify(1,x,n,y);78         else {79             LL ans=0;80             ans=query(1,x,y)-query(1,x-1,x-1)*(y-x+1);81             printf("%lld\n",ans);82         }83     }84     return 0;85 }86 87 int sb=hh();88 int main(int argc,char**argv) {;}