【9018:1956】線段樹1

問題 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表示閉區間的左右端點

輸出

輸出共有若干行，對于每一個詢問輸出一個整數結果

樣例輸入

樣例輸出

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\n",query(1,n,x,y,1,2));
56         if(num==3) printf("%d\n",query(1,n,x,y,1,3));
57         if(num==4) printf("%d\n",query(1,n,x,y,1,4));
58     }
59     return 0;
60 }

轉載于:https://www.cnblogs.com/Beginner-/p/7467737.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/251916.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/251916.shtml
英文地址，請注明出處：http://en.pswp.cn/news/251916.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！