题目描述 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分的用户表示诚挚的歉意
思路：
裸线段树；
轻松ac；
来，上代码：
#include <cstdio> #include <iostream> #include <algorithm> #define maxn 100001 #define LL long long using namespace std; struct TreeNodeType { LL l,r,mid,dis,max_,min_,flag,flag_; bool if_; }; struct TreeNodeType tree[maxn<<2]; LL if_z,n,m; char Cget; inline void read_int(LL &now) { now=0,if_z=1,Cget=getchar(); while(Cget<'0'||Cget>'9') { if(Cget=='-') if_z=-1; Cget=getchar(); } while(Cget>='0'&&Cget<='9') { now=now*10+Cget-'0'; Cget=getchar(); } now*=if_z; } inline void tree_up(LL now) { tree[now].dis=tree[now<<1].dis+tree[now<<1|1].dis; tree[now].max_=max(tree[now<<1].max_,tree[now<<1|1].max_); tree[now].min_=min(tree[now<<1].min_,tree[now<<1|1].min_); } inline void tree_down(LL now) { if(tree[now].l==tree[now].r) return ; if(tree[now].if_) { tree[now<<1].flag=0,tree[now<<1].flag_=tree[now].flag_; tree[now<<1].if_=true,tree[now<<1].max_=tree[now].flag_; tree[now<<1].min_=tree[now].flag_; tree[now<<1].dis=(tree[now<<1].r-tree[now<<1].l+1)*tree[now].flag_; tree[now<<1|1].flag=0,tree[now<<1|1].flag_=tree[now].flag_; tree[now<<1|1].if_=true,tree[now<<1|1].max_=tree[now].flag_; tree[now<<1|1].min_=tree[now].flag_; tree[now<<1|1].dis=(tree[now<<1|1].r-tree[now<<1|1].l+1)*tree[now].flag_; } else { if(tree[now<<1].if_) { tree[now<<1].max_+=tree[now].flag; tree[now<<1].min_+=tree[now].flag; tree[now<<1].flag_+=tree[now].flag; tree[now<<1].dis+=(tree[now<<1].r-tree[now<<1].l+1)*tree[now].flag; } else { tree[now<<1].max_+=tree[now].flag; tree[now<<1].min_+=tree[now].flag; tree[now<<1].flag+=tree[now].flag; tree[now<<1].dis+=(tree[now<<1].r-tree[now<<1].l+1)*tree[now].flag; } if(tree[now<<1|1].if_) { tree[now<<1|1].max_+=tree[now].flag; tree[now<<1|1].min_+=tree[now].flag; tree[now<<1|1].flag_+=tree[now].flag; tree[now<<1|1].dis+=(tree[now<<1|1].r-tree[now<<1|1].l+1)*tree[now].flag; } else { tree[now<<1|1].max_+=tree[now].flag; tree[now<<1|1].min_+=tree[now].flag; tree[now<<1|1].flag+=tree[now].flag; tree[now<<1|1].dis+=(tree[now<<1|1].r-tree[now<<1|1].l+1)*tree[now].flag; } } tree[now].flag=0,tree[now].flag_=0,tree[now].if_=false; } void tree_build(LL now,LL l,LL r) { tree[now].l=l,tree[now].r=r; if(l==r) { read_int(tree[now].dis); tree[now].max_=tree[now].dis; tree[now].min_=tree[now].dis; return ; } tree[now].mid=(l+r)>>1; tree_build(now<<1,l,tree[now].mid); tree_build(now<<1|1,tree[now].mid+1,r); tree_up(now); } void tree_change(LL now,LL l,LL r,LL x) { if(tree[now].l==l&&tree[now].r==r) { if(tree[now].if_) tree[now].flag_+=x; else tree[now].flag+=x; tree[now].dis+=(r-l+1)*x; tree[now].max_+=x; tree[now].min_+=x; return ; } if(tree[now].flag||tree[now].if_) tree_down(now); if(l>tree[now].mid) tree_change(now<<1|1,l,r,x); else if(r<=tree[now].mid) tree_change(now<<1,l,r,x); else { tree_change(now<<1,l,tree[now].mid,x); tree_change(now<<1|1,tree[now].mid+1,r,x); } tree_up(now); } void tree_change_(LL now,LL l,LL r,LL x) { if(tree[now].l==l&&tree[now].r==r) { tree[now].if_=true; tree[now].flag_=x; tree[now].dis=(r-l+1)*x; tree[now].max_=x; tree[now].min_=x; return ; } if(tree[now].flag||tree[now].if_) tree_down(now); if(l>tree[now].mid) tree_change_(now<<1|1,l,r,x); else if(r<=tree[now].mid) tree_change_(now<<1,l,r,x); else { tree_change_(now<<1,l,tree[now].mid,x); tree_change_(now<<1|1,tree[now].mid+1,r,x); } tree_up(now); } LL tree_query(LL now,LL l,LL r,LL type) { if(tree[now].l==l&&tree[now].r==r) { if(type==1) return tree[now].dis; if(type==2) return tree[now].max_; if(type==3) return tree[now].min_; } if(tree[now].flag||tree[now].if_) tree_down(now); tree_up(now); if(l>tree[now].mid) return tree_query(now<<1|1,l,r,type); else if(r<=tree[now].mid) return tree_query(now<<1,l,r,type); else { if(type==1) return tree_query(now<<1,l,tree[now].mid,type)+tree_query(now<<1|1,tree[now].mid+1,r,type); if(type==2) return max(tree_query(now<<1,l,tree[now].mid,type),tree_query(now<<1|1,tree[now].mid+1,r,type)); if(type==3) return min(tree_query(now<<1,l,tree[now].mid,type),tree_query(now<<1|1,tree[now].mid+1,r,type)); } } int main() { read_int(n),read_int(m); tree_build(1,1,n); char ch[10]; for(LL i=1;i<=m;i++) { cin>>ch; LL x,y,z; if(ch[0]=='a') { read_int(x),read_int(y),read_int(z); tree_change(1,x,y,z); } else if(ch[0]=='s') { if(ch[1]=='e') { read_int(x),read_int(y),read_int(z); tree_change_(1,x,y,z); } else { read_int(x),read_int(y); cout<<tree_query(1,x,y,1); putchar(' '); } } else if(ch[0]=='m') { if(ch[1]=='a') { read_int(x),read_int(y); cout<<tree_query(1,x,y,2); putchar(' '); } else { read_int(x),read_int(y); cout<<tree_query(1,x,y,3); putchar(' '); } } } return 0; }