题目分析
看题面可以知道题目的要求：
对于一个长度为N的序列a支持以下操作
1.令所有满足l<=i<=r的ai全部变为ai*c。
2.令所有满足l<=i<=r的ai全部变为ai+c。
3.求所有满足l<=i<=r的ai的和。
显然这是对一个区间做加法和乘法的操作，可以使用线段树完成。
联想只有区间加法的过程，对于线段树上的一个节点，我们设sum表示该区间的和，inc表示该区间每个数要加上的数，那么该节点所表示的区间和为sum + inc * (r - l + 1)
属于x+bx+b这种形式，(r - l + 1)(r−l+1)可以看作常数。
但是现在区间不仅有加法，还有乘法，因此很容易想到区间和的形式应该为：ax+bax+b
表示现在的区间和是原来的区间和先乘以a再加上b。
在程序中我们把mtp定义为a，sum定义为x，inc定义为b，下传标记时节点的更新就是sum = mtp * sum + inc
区间修改
当我们要修改一个区间时，要保证ax+b的形式，即先乘后加的形式。当将区间乘以一个数k时，原来的区间和为ax+bax+b，乘以k得k(ax+b)=kax+kbk(ax+b)=kax+kb，也就是把节点的inc和mtp都乘上一个k。
区间加一个数更加简单，原来的区间和为ax+bax+b，加上一个k为ax+b+kax+b+k，合并b, k得ax+(b+k)ax+(b+k)，也就是把原来的inc加上一个k。
标记下传
我们设要下传标记的节点的inc为bb，sum为xx，mtp为aa，因此这个节点的和为ax+bax+b，它的一个儿子的inc为b'b′，sum为yy，mtp为a'a′，这个节点的和为a'y+b'a′y+b′，为了保持先乘后加的顺序，先把该节点的和乘以aa得aa'y+ab'aa′y+ab′然后加上b得aa'y+ab'+baa′y+ab′+b合并一下得(aa')y+(ab'+b)(aa′)y+(ab′+b)也就是把这个节点的儿子的mtp乘以这个节点的mtp，然后把这个节点的儿子的inc乘以这个节点的mtp再加上这个节点的inc，更新这个节点，清空这个节点的标记，然后标记就下传完毕了。
#include<stdio.h> #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ll long long const int manx = 100011; ll sum[manx<<2],la[manx<<2],n,p; void PushUP(int rt) { sum[rt] = sum[rt<<1] + sum[rt<<1|1]; } void build(int l,int r,int rt) { la[rt]=0; if(l==r) { scanf("%lld",&sum[rt]); return ; } int m = (l+r) >> 1; build(lson); build(rson); PushUP(rt); } void PushDown(int rt,int m) { if(la[rt]) { la[rt<<1]+=la[rt]; la[rt<<1|1]+=la[rt]; sum[rt<<1]+=la[rt]*(m-(m>>1)); sum[rt<<1|1]+=la[rt]*(m>>1); la[rt]=0; } } void update(int L,int R,int c,int l,int r,int rt) { if(L<=l&&r<=R) { la[rt]+=c; sum[rt]+=(ll)c*(r-l+1); return ; } PushDown(rt,r-l+1); int m=(l+r)>>1; if(L<=m) update(L,R,c,lson); if(R>m) update(L,R,c,rson); PushUP(rt); } ll query(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) { return sum[rt]; } PushDown(rt,r-l+1); ll res=0; int m=(l+r)>>1; if(L<=m) res+=query(L,R,lson); if(R>m) res+=query(L,R,rson); return res; } int main( ) { scanf("%lld%lld",&n,&p); build(1,n,1); scanf("%d",&m); while(m--) { int op; scanf("%d",&op); if(op==1) { } else if(op==2) { scanf("%d%d%d",&l,&r,&c); update(l,r,c,1,n,1); } } }