题解 | #数据结构#

思路

要维护区间和以及平方和两个线段树，同时支持加法和乘法操作。
前面基本套模板就行了，那么我们重点是pushdown怎么写。
（这个板子是参照oi-wiki先打出lazy的pushdown的，已经能支持加法维护区间和了）
我们可以用上述式子Pushdown区间平方和。
考虑乘法：
一开始我们建立cheng记录结点需要pushdown的乘数，在往下传递的过程中

这样两个线段树的更新操作就完成了。

代码

#include<bits/stdc++.h>
#define int ll
typedef long long ll; 
using namespace std;
const int maxn=10005;
int n,m,opt,l,r,x;
int num[maxn],tree[maxn*4],fang[maxn*4];
int lazy[maxn*4],cheng[maxn*4];

inline void read(int &data){
    int x=0,flag=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') flag=flag*-1;
        ch=getchar(); 
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    data=x*flag;
} 

void pushdown(int node,int start,int end){
    int mid=start+end>>1;
    lazy[node<<1]*=cheng[node];
    lazy[node<<1|1]*=cheng[node];
    cheng[node<<1]*=cheng[node];
    cheng[node<<1|1]*=cheng[node];
    tree[node<<1]*=cheng[node];
    tree[node<<1|1]*=cheng[node];
    fang[node<<1]*=cheng[node]*cheng[node];
    fang[node<<1|1]*=cheng[node]*cheng[node];
    cheng[node]=1;
    if(lazy[node]){
        lazy[node<<1]+=lazy[node];
        lazy[node<<1|1]+=lazy[node]; 
        fang[node<<1]+=2*lazy[node]*tree[node<<1]+(mid-start+1)*lazy[node]*lazy[node];
        fang[node<<1|1]+=2*lazy[node]*tree[node<<1|1]+(end-mid)*lazy[node]*lazy[node];
        tree[node<<1]+=lazy[node]*(mid-start+1);
        tree[node<<1|1]+=lazy[node]*(end-mid);
        lazy[node]=0;
    }
}

void pushup(int node){
    tree[node]=tree[node<<1]+tree[node<<1|1];
    fang[node]=fang[node<<1]+fang[node<<1|1];
}

void build(int node,int start,int end){
    lazy[node]=0;cheng[node]=1;
    if(start==end){
        tree[node]=num[start];
        fang[node]=tree[node]*tree[node];
        return;
    }
    int mid=start+end>>1;
    build(node<<1,start,mid);
    build(node<<1|1,mid+1,end);
    pushup(node);
}

int query1(int node,int start,int end,int l,int r){
    if(l<=start&&end<=r) return tree[node];
    int mid=start+end>>1;
    pushdown(node,start,end);
    int res=0;
    if(l<=mid) res+=query1(node<<1,start,mid,l,r);
    if(r>mid) res+=query1(node<<1|1,mid+1,end,l,r);
    return res; 
}


int query2(int node,int start,int end,int l,int r){
    if(l<=start&&end<=r) return fang[node];
    int mid=start+end>>1;
    pushdown(node,start,end);
    int res=0;
    if(l<=mid) res+=query2(node<<1,start,mid,l,r);
    if(r>mid) res+=query2(node<<1|1,mid+1,end,l,r);
    return res; 
}

void add(int node,int start,int end,int l,int r,int val){
    if(l<=start&&end<=r){
        lazy[node]+=val;
        fang[node]+=2*val*tree[node]+(end-start+1)*val*val;
        tree[node]+=(end-start+1)*val;
        return;
    }
    int mid=start+end>>1;
    pushdown(node,start,end);
    if(l<=mid) add(node<<1,start,mid,l,r,val);
    if(r>mid) add(node<<1|1,mid+1,end,l,r,val);
    pushup(node);
}

void multi(int node,int start,int end,int l,int r,int val){
    if(l<=start&&end<=r){
        lazy[node]*=val;
        cheng[node]*=val;
        tree[node]*=val;
        fang[node]*=val*val;
        return;
    }
    int mid=start+end>>1;
    pushdown(node,start,end);
    if(l<=mid) multi(node<<1,start,mid,l,r,val);
    if(r>mid) multi(node<<1|1,mid+1,end,l,r,val);
    pushup(node);
}

signed main(){
    read(n);read(m);
    for(int i=1;i<=n;i++)    read(num[i]);
    build(1,1,n);
    for(int i=1;i<=m;i++){
        read(opt);
        if(opt==1){
            read(l);read(r);
            printf("%lld\n",query1(1,1,n,l,r));
        }
        if(opt==2){
            read(l);read(r);
            printf("%lld\n",query2(1,1,n,l,r));
        }
        if(opt==3){
            read(l);read(r);read(x);
            multi(1,1,n,l,r,x);
        }
        if(opt==4){
            read(l);read(r);read(x);
            add(1,1,n,l,r,x);            
        }
    }
    return 0;
}