问题 D: 【模板】线段树1
时间限制: 1 Sec 内存限制: 512 MB提交: 80 解决: 40
[提交][状态][讨论版]
题目描述
给定一个无序数列，有四种操作：
1.令数列中的某个数加上某个数
2.求一个区间的和
3.查询一段区间内的最大值；
4.查询一段区间内的最小值；
输入
输入的第1行，共有两个数n和q，表示数列长度和操作次数
输入的第2行，共有n个数，表示该数列
接下来共有q行，每行有三个数
第1个数为操作类型，具体如下
若是第1种操作，接下来两个数x，y分别表示将第x个数加y
若是第2～4种操作，接下来两个数x，y表示闭区间的左右端点
输出
输出共有若干行，对于每一个询问输出一个整数结果
样例输入
5 4
1 2 3 4 5
2 1 4
1 3 -2
3 1 5
4 2 3
样例输出
10
5
1
提示
1<=n,q<=200000
保证所有数据在c/c++语言的INT范围内，pascal语言的longint范围内。
题解：线段树模板题，这个模板可支持区间加减。
代码如下：
1 #include<cstdio> 2 #include<iostream> 3 #define Max 200000 4 using namespace std; 5 int n,q; 6 struct node{ 7 int maxn,minn,sum,mark; 8 }tree[Max*3]; 9 void pushdown(int k,int l,int r){ 10 tree[2*k].mark+=tree[k].mark; 11 tree[2*k+1].mark+=tree[k].mark; 12 int len=r-l+1; 13 tree[2*k].sum+=tree[k].mark*(len-len/2); 14 tree[2*k+1].sum+=tree[k].mark*(len/2); 15 tree[k].mark=0; 16 } 17 void update(int l,int r,int a,int b,int k,int add){ 18 if(a<=l&&b>=r){ 19 tree[k].maxn+=add; tree[k].minn+=add; 20 tree[k].sum+=(r-l+1)*add; return; 21 } 22 if(l!=r&&tree[k].mark) pushdown(k,l,r); 23 int mid=(l+r)/2; 24 if(a<=mid) update(l,mid,a,b,2*k,add); 25 if(b>mid) update(mid+1,r,a,b,2*k+1,add); 26 tree[k].maxn=max(tree[2*k].maxn,tree[2*k+1].maxn); 27 tree[k].minn=min(tree[2*k].minn,tree[2*k+1].minn); 28 tree[k].sum=tree[2*k].sum+tree[2*k+1].sum; 29 } 30 int query(int l,int r,int a,int b,int k,int num){ 31 if(a==l&&b==r){ 32 if(num==3) return tree[k].maxn; 33 if(num==4) return tree[k].minn; 34 if(num==2) return tree[k].sum; 35 } 36 if(l!=r&&tree[k].mark) pushdown(k,l,r); 37 int mid=(l+r)/2; 38 if(b<=mid) return query(l,mid,a,b,2*k,num); 39 else if(a>mid) return query(mid+1,r,a,b,2*k+1,num); 40 else{ 41 if(num==3) return max(query(l,mid,a,mid,2*k,num),query(mid+1,r,mid+1,b,2*k+1,num)); 42 if(num==4) return min(query(l,mid,a,mid,2*k,num),query(mid+1,r,mid+1,b,2*k+1,num)); 43 if(num==2) return query(l,mid,a,mid,2*k,num)+query(mid+1,r,mid+1,b,2*k+1,num); 44 } 45 } 46 int main() 47 { 48 scanf("%d%d",&n,&q); 49 for(int i=1;i<=n;i++){ 50 int a; scanf("%d",&a); update(1,n,i,i,1,a); 51 } 52 for(int i=1;i<=q;i++){ 53 int num,x,y; scanf("%d%d%d",&num,&x,&y); 54 if(num==1) update(1,n,x,x,1,y); 55 if(num==2) printf("%d ",query(1,n,x,y,1,2)); 56 if(num==3) printf("%d ",query(1,n,x,y,1,3)); 57 if(num==4) printf("%d ",query(1,n,x,y,1,4)); 58 } 59 return 0; 60 }