1008-数据结构_2021秋季算法入门班第十一章习题：线段树、树状数组 (nowcoder.com)

题意：

思路：

线段树应用的一般思路：

1. 先去确定需要维护几个序列（一个序列对应一棵线段树）

2. 再去确定对于一个序列需要维护的东西

3. 再去考虑计算修改操作对需要维护的答案的贡献需要什么信息，这些信息就是新的需要维护的东西

4. 这样对于一个序列所有需要维护的东西就确定了

5. 去pushdown里计算修改操作对一棵线段树里的各种tag的贡献，考虑lazy tag的时候考虑要加哪些lazy tag，这个一定是和操作性质有关的，且维护的是序列里每一个数的信息

6. 去pushup考虑怎么从两个子区间得到一个大区间

对于这道题：

1. 首先我们需要维护的两个序列，一个是原序列，一个是原序列的平方和

2. 对于这两个序列，我们需要维护的都是区间和

3. 考虑修改操作。这里有三种修改操作：+x，*x，*y+x

考虑+x:

对于第一个序列，加上add这个lazy tag就可以了

对于第二个序列，我们这样去计算贡献：

可以看到我们用tree1的区间和和x和区间长度这些信息就能算出贡献，因此不需要额外加tag

考虑*x：

对于第一个序列，我们需要加mul这个lazy tag

对于第二个序列，这样去计算贡献：

贡献可以直接*y*y

还有一种操作:*y+x：

计算一下贡献就是：

这样我们一共需要维护哪些tag就确定了

4. 然后就是最重要的一步，在pushdown里根据父结点计算贡献

注意要先算tree2的贡献再算tree1的贡献，因为计算tree2的贡献需要用到旧的tree1，不能先更新tree1再更新tree2

5. 最后pushup就是很简单的左区间+右区间

Code：

#include 
#define int long long
const int mxn=1e5+10;
const int mxe=2e5+10;
const int mod=1e9+7;
const int Mnf=1e18;
const int Inf=-1e18;
using namespace std;
struct Tree{int sum,add,mul;
}tree1[mxe<<2],tree2[mxe<<2];int n,m,op,l,r,x;
int a[mxn];
void pushup(int rt){tree1[rt].sum=tree1[rt<<1].sum+tree1[rt<<1|1].sum;tree2[rt].sum=tree2[rt<<1].sum+tree2[rt<<1|1].sum;
}
void build(int rt,int l,int r){tree1[rt].add=tree2[rt].add=0;tree2[rt].mul=tree2[rt].mul=1;if(l==r){tree1[rt].sum=a[l];tree2[rt].sum=a[l]*a[l];return;}int mid=l+r>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);pushup(rt);
}
void pushdown(int rt,int tot){int x=tree2[rt].add,y=tree2[rt].mul;//区间乘：tree2[rt<<1].add=tree2[rt<<1].add*y+x;tree2[rt<<1|1].add=tree2[rt<<1|1].add*y+x;tree2[rt<<1].mul*=y;tree2[rt<<1|1].mul*=y;tree2[rt<<1].sum=tree2[rt<<1].sum*y*y+2*x*y*tree1[rt<<1].sum+x*x*(tot-tot/2);tree2[rt<<1|1].sum=tree2[rt<<1|1].sum*y*y+2*x*y*tree1[rt<<1|1].sum+x*x*(tot/2);//区间和：tree1[rt<<1].add=tree1[rt<<1].add*y+x;tree1[rt<<1|1].add=tree1[rt<<1|1].add*y+x;tree1[rt<<1].mul*=y;tree1[rt<<1|1].mul*=y;tree1[rt<<1].sum=tree1[rt<<1].sum*y+(tot-tot/2)*x;tree1[rt<<1|1].sum=tree1[rt<<1|1].sum*y+(tot/2)*x;tree1[rt].add=tree2[rt].add=0;tree1[rt].mul=tree2[rt].mul=1;
}
void modify_sum(int rt,int l,int r,int x,int y,int k){if(x<=l&&r<=y){tree1[rt].add+=k;tree2[rt].add+=k;tree2[rt].sum+=2*tree1[rt].sum*k+(r-l+1)*k*k;tree1[rt].sum+=k*(r-l+1);return;}if(tree1[rt].add||tree1[rt].mul!=1) pushdown(rt,r-l+1);int mid=l+r>>1;if(x<=mid) modify_sum(rt<<1,l,mid,x,y,k);if(y>mid) modify_sum(rt<<1|1,mid+1,r,x,y,k);pushup(rt);
}
void modify_mul(int rt,int l,int r,int x,int y,int k){if(x<=l&&r<=y){tree1[rt].add*=k;tree2[rt].add*=k;tree1[rt].mul*=k;tree2[rt].mul*=k;tree1[rt].sum*=k;tree2[rt].sum*=k*k;return;}if(tree1[rt].add||tree1[rt].mul!=1) pushdown(rt,r-l+1);int mid=l+r>>1;if(x<=mid) modify_mul(rt<<1,l,mid,x,y,k);if(y>mid) modify_mul(rt<<1|1,mid+1,r,x,y,k);pushup(rt);
}
int query(int rt,int l,int r,int x,int y,Tree *tree){if(x<=l&&r<=y){return tree[rt].sum;}pushdown(rt,r-l+1);int mid=l+r>>1;int res=0;if(x<=mid) res+=query(rt<<1,l,mid,x,y,tree);if(y>mid) res+=query(rt<<1|1,mid+1,r,x,y,tree);return res; 
}
void solve(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];build(1,1,n);for(int i=1;i<=m;i++){cin>>op;if(op==1){cin>>l>>r;cout<>l>>r;cout<>l>>r>>x;modify_mul(1,1,n,l,r,x);}else{cin>>l>>r>>x;modify_sum(1,1,n,l,r,x);}}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;while(__--)solve();return 0;
}