题目描述 Description
有n个数和5种操作
add a b c：把区间[a,b]内的所有数都增加c
set a b c：把区间[a,b]内的所有数都设为c
sum a b：查询区间[a,b]的区间和
max a b：查询区间[a,b]的最大值
min a b：查询区间[a,b]的最小值
输入描述 Input Description
第一行两个整数n，m，第二行n个整数表示这n个数的初始值
接下来m行操作，同题目描述
输出描述 Output Description
对于所有的sum、max、min询问，一行输出一个答案
样例输入 Sample Input
10 6
3 9 2 8 1 7 5 0 4 6
add 4 9 4
set 2 6 2
add 3 8 2
sum 2 10
max 1 7
min 3 6
样例输出 Sample Output
49
11
4
数据范围及提示 Data Size & Hint
10%:1<n,m<=10
30%:1<n,m<=10000
100%:1<n,m<=100000
保证中间结果在long long(C/C++)、int64(pascal)范围内
PS:由于数据6出错导致某些人只有90分，已于2016.5.13修正。
出题人在此对两位90分的用户表示诚挚的歉意
线段树覆盖、增加标记同时下放
一种可行的下放规律：
一、打标记
增加标记直接打，覆盖标记打上标记后，原有的增加标记清0
二、下放标记
1、先下放覆盖标记，再下放增加标记
2、增加标记直接加，覆盖标记下放后，下放点的增加标记清0
小提示：判断 是否有覆盖标记、覆盖标记是啥 要用2个变量
否则覆盖标记若为0，错误判断成没有标记
#include<cstdio> #include<algorithm> #define N 100001 using namespace std; int n,m,x,y; long long z; long long ans; struct node { int l,r,siz; long long set,add,minn,maxn,sum; bool v; }tr[N*4]; void up(int k) { tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum; tr[k].maxn=max(tr[k<<1].maxn,tr[k<<1|1].maxn); tr[k].minn=min(tr[k<<1].minn,tr[k<<1|1].minn); } void build(int k,int l,int r) { tr[k].l=l; tr[k].r=r; tr[k].siz=r-l+1; if(l==r) { scanf("%d",&x); tr[k].sum=tr[k].maxn=tr[k].minn=x; return ; } int mid=l+r>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); up(k); } void down_set(int k) { int l=k<<1,r=k<<1|1; tr[l].add=tr[r].add=0; tr[l].set=tr[r].set=tr[k].set; tr[l].v=tr[r].v=true; tr[l].maxn=tr[r].maxn=tr[l].minn=tr[r].minn=tr[k].set; tr[l].sum=tr[l].siz*tr[k].set; tr[r].sum=tr[r].siz*tr[k].set; tr[k].v=tr[k].set=0; } void down_add(int k) { int l=k<<1,r=k<<1|1; tr[l].maxn+=tr[k].add; tr[r].maxn+=tr[k].add; tr[l].minn+=tr[k].add; tr[r].minn+=tr[k].add; tr[l].sum+=tr[l].siz*tr[k].add; tr[r].sum+=tr[r].siz*tr[k].add; tr[l].add+=tr[k].add; tr[r].add+=tr[k].add; tr[k].add=0; } void addd(int k) { if(tr[k].l>=x&&tr[k].r<=y) { tr[k].add+=z; tr[k].maxn+=z; tr[k].minn+=z; tr[k].sum+=z*tr[k].siz; return; } if(tr[k].v) down_set(k); if(tr[k].add) down_add(k); int mid=tr[k].l+tr[k].r>>1; if(x<=mid) addd(k<<1); if(y>mid) addd(k<<1|1); up(k); } void sett(int k) { if(tr[k].l>=x&&tr[k].r<=y) { tr[k].maxn=tr[k].minn=z; tr[k].set=z; tr[k].v=true; tr[k].sum=z*tr[k].siz; tr[k].add=0; return; } if(tr[k].v) down_set(k); if(tr[k].add) down_add(k); int mid=tr[k].l+tr[k].r>>1; if(x<=mid) sett(k<<1); if(y>mid) sett(k<<1|1); up(k); } void query(int k,int w) { if(tr[k].l>=x&&tr[k].r<=y) { if(w==1) ans+=tr[k].sum; else if(w==2) ans=max(ans,tr[k].maxn); else ans=min(ans,tr[k].minn); return; } if(tr[k].v) down_set(k); if(tr[k].add) down_add(k); int mid=tr[k].l+tr[k].r>>1; if(x<=mid) query(k<<1,w); if(y>mid) query(k<<1|1,w); } int main() { scanf("%d%d",&n,&m); build(1,1,n); char ch[8]; while(m--) { scanf("%s",ch); if(ch[0]=='a') { scanf("%d%d%lld",&x,&y,&z); addd(1); } else if(ch[1]=='e') { scanf("%d%d%lld",&x,&y,&z); sett(1); } else if(ch[1]=='u') { scanf("%d%d",&x,&y); ans=0; query(1,1); printf("%lld ",ans); } else if(ch[1]=='a') { scanf("%d%d",&x,&y); ans=-1; query(1,2); printf("%lld ",ans); } else { scanf("%d%d",&x,&y); ans=1e17; query(1,3); printf("%lld ",ans); } } }
判断 是否有覆盖标记、覆盖标记是啥 要用2个变量
否则覆盖标记若为0，错误判断成没有标记