[数据结构与算法]线段树（加、乘、区间求和、区间平方和）板子

牛客竞赛数据结构专题班树状数组、线段树练习题：
D、数据结构
存个板子

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int N=1e4+7;
const ll mod=1e9+7;
#define lch (k*2)
#define rch (k*2+1)
#define mid ((l+r)/2)
ll n,p,m;
ll a[N],sum[N*4],lazy_a[N*4],lazy_m[N*4];
ll s1[N*4];
void init(ll k,ll l,ll r)
{
    if(l>=r)
    {
        lazy_m[k]=1;
        sum[k]=a[l];
        s1[k]=a[l]*a[l];
        return ;
    }
    init(lch,l,mid);
    init(rch,mid+1,r);
    sum[k]=(sum[lch]+sum[rch]);
    s1[k]=s1[lch]+s1[rch];
    lazy_m[k]=1;
}
void pushdown(ll k,ll zlen,ll ylen)
{
    if(lazy_m[k]!=1){
        
        lazy_m[lch]=(lazy_m[lch]*lazy_m[k]);
        lazy_m[rch]=(lazy_m[rch]*lazy_m[k]);
        lazy_a[lch]=(lazy_a[lch]*lazy_m[k]);
        lazy_a[rch]=(lazy_a[rch]*lazy_m[k]);
        sum[lch]=(sum[lch]*lazy_m[k]);
        sum[rch]=(sum[rch]*lazy_m[k]);
        s1[lch]*=lazy_m[k]*lazy_m[k];
        s1[rch]*=lazy_m[k]*lazy_m[k];
        lazy_m[k]=1;
    }
    if(lazy_a[k]){
        s1[lch]+=(2*lazy_a[k]*sum[lch]+lazy_a[k]*lazy_a[k]*(zlen));
        s1[rch]+=(2*lazy_a[k]*sum[rch]+lazy_a[k]*lazy_a[k]*(ylen));
        sum[lch]=(sum[lch]+zlen*lazy_a[k]);
        sum[rch]=(sum[rch]+ylen*lazy_a[k]);
        lazy_a[lch]=(lazy_a[lch]+lazy_a[k]);
        lazy_a[rch]=(lazy_a[rch]+lazy_a[k]);
        lazy_a[k]=0;
    }
}
void add(ll k,ll l,ll r,ll ql,ll qr,ll val)
{
    if(l>=ql&&r<=qr)
    {
        s1[k]=s1[k]+2*val*sum[k]+(r-l+1)*val*val;
        lazy_a[k]=(lazy_a[k]+val);
        sum[k]=(sum[k]+val*(r-l+1));
        return ;
    }
    pushdown(k,mid-l+1,r-mid);
    if(ql<=mid)
        add(lch,l,mid,ql,qr,val);
    if(mid+1<=qr)
        add(rch,mid+1,r,ql,qr,val);
    sum[k]=(sum[lch]+sum[rch]);
    s1[k]=s1[lch]+s1[rch];
}
void mul(ll k,ll l,ll r,ll ql,ll qr,ll val)
{
    if(l>=ql&&r<=qr)
    {
        s1[k]=val*val*s1[k];
        lazy_m[k]=lazy_m[k]*val;
        lazy_a[k]=lazy_a[k]*val;
        sum[k]=(sum[k]*val);
        return ;
    }
    pushdown(k,mid-l+1,r-mid);
    if(ql<=mid)
        mul(lch,l,mid,ql,qr,val);
    if(mid+1<=qr)
        mul(rch,mid+1,r,ql,qr,val);
    sum[k]=(sum[lch]+sum[rch]);
    s1[k]=s1[lch]+s1[rch];
}
ll qry(ll k,ll l,ll r,ll ql,ll qr)
{
    if(l>=ql&&r<=qr)
    {
        return sum[k];
    }
    pushdown(k,mid-l+1,r-mid);
    ll mx1=0,mx2=0;
    if(ql<=mid)
    {
        mx1=qry(lch,l,mid,ql,qr);
    }
    if(mid+1<=qr)
    {
        mx2=qry(rch,mid+1,r,ql,qr);
    }
    return (mx1+mx2);
}
ll qry1(ll k,ll l,ll r,ll ql,ll qr)
{
    if(l>=ql&&r<=qr)
    {
        return s1[k];
    }
    pushdown(k,mid-l+1,r-mid);
    ll mx1=0,mx2=0;
    if(ql<=mid)
    {
        mx1=qry1(lch,l,mid,ql,qr);
    }
    if(mid+1<=qr)
    {
        mx2=qry1(rch,mid+1,r,ql,qr);
    }
    //cout<<mx1<<" "<<mx2<<endl;
    return (mx1+mx2);
}
int main()
{
    ios::sync_with_stdio(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    init(1,1,n);
    //cout<<s3[4]<<' '<<s3[5]<<endl;
    while(m--)
    {
        int op,l,r,x;
        cin>>op;
        if(op==1)
        {
            cin>>l>>r;
            cout<<qry(1,1,n,l,r)<<endl;
        }
        if(op==2)
        {
            cin>>l>>r;
            cout<<qry1(1,1,n,l,r)<<endl;
        }
        if(op==3)
        {
            cin>>l>>r>>x;
            mul(1,1,n,l,r,x);
        }
        if(op==4)
        {
            cin>>l>>r>>x;
            add(1,1,n,l,r,x);
        }
    }
}