問(wèn)題 D: 【模板】線段樹1

時(shí)間限制: 1 Sec??內(nèi)存限制: 512 MB
提交: 80??解決: 40
[提交][狀態(tài)][討論版]

題目描述

給定一個(gè)無(wú)序數(shù)列，有四種操作：

1.令數(shù)列中的某個(gè)數(shù)加上某個(gè)數(shù)

2.求一個(gè)區(qū)間的和

3.查詢一段區(qū)間內(nèi)的最大值；

4.查詢一段區(qū)間內(nèi)的最小值；

輸入

輸入的第1行，共有兩個(gè)數(shù)n和q，表示數(shù)列長(zhǎng)度和操作次數(shù)

輸入的第2行，共有n個(gè)數(shù)，表示該數(shù)列

接下來(lái)共有q行，每行有三個(gè)數(shù)

第1個(gè)數(shù)為操作類型，具體如下

若是第1種操作，接下來(lái)兩個(gè)數(shù)x，y分別表示將第x個(gè)數(shù)加y

若是第2～4種操作，接下來(lái)兩個(gè)數(shù)x，y表示閉區(qū)間的左右端點(diǎn)

輸出

輸出共有若干行，對(duì)于每一個(gè)詢問(wèn)輸出一個(gè)整數(shù)結(jié)果

樣例輸入

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

保證所有數(shù)據(jù)在c/c++語(yǔ)言的INT范圍內(nèi)，pascal語(yǔ)言的longint范圍內(nèi)。

題解：線段樹模板題，這個(gè)模板可支持區(qū)間加減。 代碼如下： 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 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Beginner-/p/7467737.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的【9018:1956】线段树1的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。