数据结构

#include <bits/stdc++.h>
#define IOS std::ios_base::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
using namespace std;
typedef long long ll;
const int N=10010;
int a[N];
struct ty
{
    ll sum,jia,cheng,ping; //和  +  *  平方和
}tree[4*N];
void pushup(int p, int l, int r)
{
    tree[p].sum =tree[2*p].sum + tree[2*p+1].sum;
    tree[p].ping =tree[2*p].ping + tree[2*p+1].ping;
}
void pushdown(int p, int l, int r)
{
    //先传乘法再传加法，乘标记需要改变加法标记
    //(a+b)*c =ac+bc 括号展开
    int mid = (l+r)>>1;
    ll y=tree[p].cheng;
    tree[2*p].jia *= y;
    tree[2*p+1].jia *= y;
    tree[2*p].cheng *= y;
    tree[2*p+1].cheng *= y;
    tree[2*p].sum *= y;
    tree[2*p+1].sum *= y;
    tree[2*p].ping *= y * y;
    tree[2*p+1].ping *= y * y;
    tree[p].cheng =1;//消除乘法标记！！！

    ll x=tree[p].jia;
    if( x )
    {
        tree[2*p].jia += x;
        tree[2*p+1].jia += x;

        //∑（ai+x）^2 == ∑ai^2 + 2x∑(ai^2) + 区间长度* (x^2)
        //先维护平方和，再维护和！！
        tree[2*p].ping += 2 * x * tree[2*p].sum +(mid-l+1) * x * x;
        tree[2*p+1].ping += 2 * x * tree[2*p+1].sum +(r-(mid+1)+1) * x * x;
        tree[2*p].sum += (mid-l+1) * x;
        tree[2*p+1].sum += (r-(mid+1)+1) * x;
        //标记一定记得清除！！
        tree[p].jia=0;
    }
}
void bulid(int p ,int l ,int r)
{
    tree[p].jia=0;
    tree[p].cheng=1;
    if( l == r)
    {
        tree[p].sum = a[l];
        tree[p].ping = a[l] * a[l];
        return ;
    }
    int mid=(l + r) >> 1;
    bulid(2*p,l,mid);
    bulid(2*p+1,mid+1,r);
    pushup(p,l,r);
}
void change(int p, int l, int r ,int a, int b, int num)
{
    if(a <= l && r <= b)
    {
        tree[p].jia += num;
        //先处理平方和，再处理和
        tree[p].ping += 2 * num * tree[p].sum +(r-l+1) * num * num;
        tree[p].sum += (r-l+1) * num;
        return ;
    }
    if( tree[p].jia || tree[p].cheng!=1 )  pushdown(p,l,r);
    int mid = (l+r) >> 1;

    if( a <= mid )    change(2*p, l,mid,a,b,num);
    if( b > mid )   change(2*p+1, mid+1, r,a,b,num);
    pushup(p,l,r);
}

void cheng(int p, int l, int r ,int a, int b, int num)
{
    if(a <= l && r <= b)
    {
        tree[p].cheng *= num;
        tree[p].jia *= num;
        tree[p].sum *= num; //区间每个元素乘num，即对区间和乘num
        tree[p].ping *= num * num; //区间乘num方
        return ;
    }
    if( tree[p].jia || tree[p].cheng!=1 )  pushdown(p,l,r);
    int mid = (l+r) >> 1;

    if( a <= mid )    cheng(2*p, l,mid,a,b,num);
    if( b > mid )   cheng(2*p+1, mid+1, r,a,b,num);
    pushup(p,l,r);
}

ll findsum(int p,int l,int r ,int a ,int b)
{
    if(a <= l && r <= b)
    {
        return tree[p].sum;
    }
    if( tree[p].jia || tree[p].cheng!=1 )  pushdown(p,l,r);
    int mid = (l+r) >> 1;
    ll res=0;
    if( a <= mid )    {res+=findsum(2*p, l,mid,a,b);}
    if( b > mid )   {res+=findsum(2*p+1, mid+1, r,a,b);}

    return res;
}
ll findping(int p,int l,int r ,int a ,int b)
{
    if(a <= l && r <= b)    return tree[p].ping;

    if( tree[p].jia || tree[p].cheng!=1 )  pushdown(p,l,r);
    int mid = (l+r) >> 1;
    ll res=0;
    if( a <= mid )    {res+=findping(2*p, l,mid,a,b);}
    if( b > mid )   {res+=findping(2*p+1, mid+1, r,a,b);}
    return res;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1 ;i<=n ;i++)
        cin>>a[i];
    //建树
    bulid(1,1,n);
    for(int i=1 ;i<=m ;i++)
    {
        int op,x,y,z;
        cin>>op>>x>>y;
        if( op == 1)
            cout<<findsum(1,1,n,x,y)<<endl;

        if( op == 2)
            cout<<findping(1,1,n,x,y)<<endl;
        if( op == 3)
        {
            cin>>z;
            cheng(1,1,n,x,y,z);
        }
        if( op == 4)
        {
            cin>>z;
            change(1,1,n,x,y,z);
        }
    }
}