平方和

总时间限制: 3000ms 内存限制: 65536kB

描述

给出n(1<=n<=500000)个数字，下标从1开始

执行m(1<=m<=500000)次操作，操作可分为两种：

1 l r x:将区间[l,r]内的每个数加上x  1<=l<=r<=n -100<=x<=100

2 l r:输出区间[l,r]内每个数平方之和

 

输入

多组输入
第一行两个整数n m
第二行n个整数
余下m行表示m个操作意义叙述于上

输出

对应每个2操作输出相应的值

样例输入

5 31 1 1 1 12 1 51 1 5 12 1 5

样例输出

520

线段树成段更新

#include<iostream>#include<cstdio>#include<cstring>using namespace std;#define N 500005#define ll long longll add[N<<2];ll sq[N<<2];ll sum[N<<2];void pushup(int rt){    sum[rt]=sum[rt<<1]+sum[rt<<1|1];    sq[rt]=sq[rt<<1]+sq[rt<<1|1];}void pushdown(int l,int r,int rt){    if(add[rt])    {        int m=(l+r)>>1;        add[rt<<1]+=add[rt];        add[rt<<1|1]+=add[rt];        sq[rt<<1]+=(2*add[rt]*sum[rt<<1]+(m-l+1)*add[rt]*add[rt]);        sq[rt<<1|1]+=(2*add[rt]*sum[rt<<1|1]+(r-m)*add[rt]*add[rt]);        sum[rt<<1]+=(m-l+1)*add[rt];        sum[rt<<1|1]+=(r-m)*add[rt];        add[rt]=0;    }}void build(int l,int r,int rt){    add[rt]=0;    if(l==r)    {        scanf("%d",&sum[rt]);        sq[rt]=sum[rt]*sum[rt];        return;    }    int m=(l+r)>>1;    build(l,m,rt<<1);    build(m+1,r,rt<<1|1);    pushup(rt);}void update(int l,int r,int rt,int L,int R,int c){    if(l==L && r==R)    {        add[rt]+=c;        sq[rt]+=2*sum[rt]*c+(r-l+1)*c*c;        sum[rt]+=(r-l+1)*c;        return;    }    int m=(l+r)>>1;    pushdown(l,r,rt);    if(R<=m) update(l,m,rt<<1,L,R,c);    else if(L>m) update(m+1,r,rt<<1|1,L,R,c);    else    {        update(l,m,rt<<1,L,m,c);        update(m+1,r,rt<<1|1,m+1,R,c);    }    pushup(rt);}ll query(int l,int r,int rt,int L,int R){    if(l==L && r==R)    {        return sq[rt];    }    int m=(l+r)>>1;    pushdown(l,r,rt);    if(R<=m) return query(l,m,rt<<1,L,R);    else if(L>m) return query(m+1,r,rt<<1|1,L,R);    else return query(l,m,rt<<1,L,m)+query(m+1,r,rt<<1|1,m+1,R);}int main(){    int n,m;    while(scanf("%d%d",&n,&m)!=EOF)    {        build(1,n,1);        while(m--)        {            int op,a,b,c;            scanf("%d",&op);            if(op==1)            {                scanf("%d%d%d",&a,&b,&c);                update(1,n,1,a,b,c);            }            else            {                scanf("%d%d",&a,&b);                printf("%lld\n",query(1,n,1,a,b));            }        }    }    return 0;}