题意

• 对于一个长为n的序列a，你需要完成q次询问，每次询问有四种情况
  1. 输出(l,r)区间和
  2. 输出(l,r)区间平方和
  3. (l,r)所有元素+=x
  4. (l,r)所有元素*=x
• 其中n为1e4量级，m为2e5量级

思路

• 线段树变种
• 对于区间和，维护第一个线段树
• 对于区间平方和，维护第二个线段树
• 对于所有元素加上定值，使用第1个lazy标记
• 对于所有元素乘上定值，使用第2个lazy标记
• 对于加法运算和乘法运算混合出出现，永远将lazy记录的式子转化为kx+b，即每次乘上一个因子s时，转化为ksx+sb
• 对于lazy标记的pushdown
  • 乘法lazy初值是1，加法初值是0
  • 先更新lazy
    • lazy_add[son]=lazy_add[son]*lazy_mul[fa]+lazy_add[fa]
    • lazy_mul[son]=lazy_mul[son]*lazy_mul[fa]
  • 然后要先转移平方的线段树，因为平方线段树依赖于正常的线段树
    • 由 变为 展开右式
    • 其中第一部分和第三部分分别对应了两个线段树的值，中间部分是
  • 最后转移正常线段树
    • 按照kx+b转移
• 对于查询，每次查询也是需要pushdown的不然会找错值
• 对于修改，修改完全包含区间的时候转移方式和pushdown类似
  • 注意lazy的转移

代码

#include<bits/stdc++.h>
#define int ll
using namespace std;
using ll=long long;
ll a[10101];
ll tre1[4*10101];
ll tre2[4*10101];
ll laz_mul[4*10101];
ll laz_add[4*10101];


void build1(int p,int l,int r){
    if(l==r){
        tre1[p]=a[l];
        return ;
    }
    int mid=(r+l)>>1;
    build1(p*2,l,mid);
    build1(p*2+1,mid+1,r);
    tre1[p]=tre1[p*2]+tre1[p*2+1];
}
void build2(int p,int l,int r){
    if(l==r){
        tre2[p]=a[l]*a[l];
        return ;
    }
    int mid=(r+l)>>1;
    build2(p*2,l,mid);
    build2(p*2+1,mid+1,r);
    tre2[p]=tre2[p*2]+tre2[p*2+1];
}
void pushdown(int p,int l,int r){
    laz_mul[p*2]*=laz_mul[p];
    laz_mul[p*2+1]*=laz_mul[p];
    laz_add[p*2]=laz_add[p*2]*laz_mul[p]+laz_add[p];
    laz_add[p*2+1]=laz_add[p*2+1]*laz_mul[p]+laz_add[p];
  
    int mid=(r+l)>>1;
    tre2[p*2]=tre2[p*2]*laz_mul[p]*laz_mul[p]+2*laz_mul[p]*laz_add[p]*tre1[p*2]+laz_add[p]*laz_add[p]*(mid-l+1);
    tre2[p*2+1]=tre2[p*2+1]*laz_mul[p]*laz_mul[p]+2*laz_mul[p]*laz_add[p]*tre1[p*2+1]+laz_add[p]*laz_add[p]*(r-mid);
    
    tre1[p*2]=tre1[p*2]*laz_mul[p]+laz_add[p]*(mid-l+1);
    tre1[p*2+1]=tre1[p*2+1]*laz_mul[p]+laz_add[p]*(r-mid);
    
    laz_add[p]=0;
    laz_mul[p]=1;
}
ll cal1(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        return tre1[p];
    }
    if(laz_add[p]!=0||laz_mul[p]!=1) pushdown(p,l,r);
    int mid=(l+r)>>1;
    if(x>mid) return cal1(p*2+1,mid+1,r,x,y);
    if(y<=mid) return cal1(p*2,l,mid,x,y);
    return cal1(p*2+1,mid+1,r,x,y)+cal1(p*2,l,mid,x,y);
}

ll cal2(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        return tre2[p];
    }
    if(laz_add[p]!=0||laz_mul[p]!=1) pushdown(p,l,r);
    int mid=(l+r)>>1;
    if(x>mid) return cal2(p*2+1,mid+1,r,x,y);
    if(y<=mid) return cal2(p*2,l,mid,x,y);
    return cal2(p*2+1,mid+1,r,x,y)+cal2(p*2,l,mid,x,y);
}

void mul(int p,int l,int r,int x,int y,int num){
    if(x<=l&&r<=y){
        tre1[p]*=num;
        tre2[p]*=num*num;
        laz_add[p]*=num;
        laz_mul[p]*=num;
        return ;
    }
    if(laz_add[p]!=0||laz_mul[p]!=1) pushdown(p,l,r);
    int mid=(r+l)>>1;
    if(x<=mid) mul(p*2,l,mid,x,y,num);
    if(y>mid) mul(p*2+1,mid+1,r,x,y,num);
    tre1[p]=tre1[p*2]+tre1[p*2+1];
    tre2[p]=tre2[p*2]+tre2[p*2+1];
}
void add(int p,int l,int r,int x,int y,int num){
    if(x<=l&&r<=y){
        tre2[p]+=num*num*(r-l+1)+2*num*tre1[p];
        tre1[p]+=(r-l+1)*num;
        laz_add[p]+=num;
        return ;
    }
    if(laz_add[p]!=0||laz_mul[p]!=1) pushdown(p,l,r);
    int mid=(r+l)>>1;
    if(x<=mid) add(p*2,l,mid,x,y,num);
    if(y>mid) add(p*2+1,mid+1,r,x,y,num);
    tre1[p]=tre1[p*2]+tre1[p*2+1];
    tre2[p]=tre2[p*2]+tre2[p*2+1];
}

signed main(){
    int n,m;
    cin >> n >> m ;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    for(int i=0;i<=4*n;i++){
        laz_add[i]=0;
        laz_mul[i]=1;
    }
    build1(1,1,n);
    build2(1,1,n);
    for(int i=0;i<m;i++){
        int op;
        cin >> op;
        if(op==1){
            int l,r;
            cin >> l >> r;
            cout << cal1(1,1,n,l,r) << endl;
        }else if(op==2){
            int l,r;
            cin >> l >> r;
            cout << cal2(1,1,n,l,r) << endl;
        }else if(op==3){
            int l,r,x;
            cin >> l >> r >> x;
            mul(1,1,n,l,r,x);
        }else{
            int l,r,x;
            cin >> l >> r >> x;
            add(1,1,n,l,r,x);
        }
    }
    return 0;
}