1476.線段樹--那個苑區(qū)的人最瘦 (10分) C時間限制：500?毫秒?|? C內(nèi)存限制：655350?Kb 題目內(nèi)容： 每年九月份開學(xué)的時候, 學(xué)校為了迎接新生, 食堂的伙食自然會比平時稍微好一些, 然而各個苑區(qū)食堂的伙食改善程度不盡相同.比如,南苑食堂的飯菜看起來就高大上一些, 而欣苑食堂的飯菜,emmmm, 我們還是去小吃街吃吧! 寶寶還在長身體呢,要吃好一點.這就可能導(dǎo)致某個苑區(qū)的學(xué)生的平均體重有所差異, 甚至差異還比較明顯. 那么問題來了, 假如我現(xiàn)在告訴你全校所有人的體重信息,然后每次操作或者是修改編號從 x 到 y的所有人的體重, 或者是詢問編號從 x 到 y 的人的平均體重, 怎么破! 輸入描述 第一行兩個正整數(shù)N,Q, 表示人數(shù)和操作次數(shù) 接下來一行有N個正整數(shù), 第i個數(shù)表示編號為i的人的初始體重(1<=i<=N) 接下來有Q行, 每行或者是0 L R X 表示編號從L到R的所有人體重改變了X, 或者是1 L R 表示詢問編號從L到R的人的平均體重 (x>0表示體重增加了,x<0表示體重減小了)對于100%的數(shù)據(jù)，滿足N<=10^6，Q<=10^4, 1<=L<=R<=N, -15<= x <=15 輸出描述 對于每組詢問, 輸出一行一個浮點數(shù)(保留兩位小數(shù))表示編號從L到R(閉區(qū)間[L,R])的人的平均體重 輸入樣例 20 10 97 126 124 83 81 81 92 99 108 114 96 103 103 92 101 116 112 93 123 122 1 1 12 0 7 19 -9 0 6 19 1 0 5 17 9 1 0 6 0 6 15 -10 1 7 12 0 12 18 12 1 6 7 1 0 8 輸出樣例 100.33 87.29 93.00 82.00 86.00 /** 線段樹模板* 區(qū)間修改 區(qū)間查詢* 版本一：當(dāng)前區(qū)間值正確，tag未下傳*/ #include<iostream> #include<cstdio> #include<queue> #include<algorithm> #include<cstring> using namespace std; typedef long long LL; const int MAXN=1e6+5; const LL INF=2e18; //const int INF=0x3f3f3f3f;//根據(jù)是否超long long修改 LL a[MAXN];//線段樹節(jié)點結(jié)構(gòu)體 struct Node{int left,right;//左右邊界LL mi,ma;//最小值 最大值LL sum;//和LL add;//增減標(biāo)記int set;//重置標(biāo)記 }tree[MAXN*4];//空間開四倍//向上更新 void PushUp(int rt){int lson=rt<<1,rson=rt<<1|1; //rt << 1 | 1 等價與 rt * 2 + 1 tree[rt].mi=min(tree[lson].mi,tree[rson].mi);tree[rt].ma=max(tree[lson].ma,tree[rson].ma);tree[rt].sum=tree[lson].sum+tree[rson].sum; }//向下傳遞標(biāo)記 void PushDown(int rt){if(tree[rt].left<tree[rt].right){//如果不是葉子int lson=rt<<1,rson=rt<<1|1;if(tree[rt].set!=-1){//set初始為一個不會重置到的數(shù)，這里是-1tree[lson].set=tree[rt].set;tree[rson].set=tree[rt].set;tree[lson].add=tree[rson].add=0;//add失效tree[lson].mi=tree[rson].mi=tree[rt].set;tree[lson].ma=tree[rson].ma=tree[rt].set;tree[lson].sum=(LL)tree[rt].set*(tree[lson].right-tree[lson].left+1);tree[rson].sum=(LL)tree[rt].set*(tree[rson].right-tree[rson].left+1);tree[rt].set=-1;}if(tree[rt].add){tree[lson].add+=tree[rt].add; tree[rson].add+=tree[rt].add;tree[lson].mi+=tree[rt].add; tree[rson].mi+=tree[rt].add;tree[lson].ma+=tree[rt].add; tree[rson].ma+=tree[rt].add;tree[lson].sum+=(LL)tree[rt].add*(tree[lson].right-tree[lson].left+1);tree[rson].sum+=(LL)tree[rt].add*(tree[rson].right-tree[rson].left+1);tree[rt].add=0;}} }//建立函數(shù) void Build(int rt,int L,int R){tree[rt].left=L;tree[rt].right=R;tree[rt].add=0;tree[rt].set=-1;if(L==R) {tree[rt].sum=tree[rt].mi=tree[rt].ma=a[L]; return;}int mid=(tree[rt].left+tree[rt].right)>>1;Build(rt<<1,L,mid);//只有Build時LR才會變Build(rt<<1|1,mid+1,R);PushUp(rt); }LL QuerySum(int rt,int L,int R){if(R<tree[rt].left||L>tree[rt].right) return 0;if(L<=tree[rt].left&&tree[rt].right<=R) return tree[rt].sum;PushDown(rt);int mid=(tree[rt].left+tree[rt].right)>>1;LL res=0;if(L<=mid) res+=QuerySum(rt<<1,L,R);if(R>mid) res+=QuerySum(rt<<1|1,L,R);PushUp(rt);return res; }LL QueryMin(int rt,int L,int R){if(L<=tree[rt].left&&tree[rt].right<=R) return tree[rt].mi;PushDown(rt);int mid=(tree[rt].left+tree[rt].right)>>1;LL res=INF;if(L<=mid) res=min(res,QueryMin(rt<<1,L,R));if(R>mid) res=min(res,QueryMin(rt<<1|1,L,R));PushUp(rt);return res; }LL QueryMax(int rt,int L,int R){if(L<=tree[rt].left&&tree[rt].right<=R) return tree[rt].ma;//完全包含才產(chǎn)生貢獻PushDown(rt);int mid=(tree[rt].left+tree[rt].right)>>1;LL res=-INF;if(L<=mid) res=max(res,QueryMax(rt<<1,L,R));if(R>mid) res=max(res,QueryMax(rt<<1|1,L,R));PushUp(rt);return res; }void UpdateAdd(int rt,int L,int R,int x){//把區(qū)間[L,R]加上xif(L<=tree[rt].left&&tree[rt].right<=R){tree[rt].add+=x;tree[rt].sum+=(LL)x*(tree[rt].right-tree[rt].left+1);tree[rt].mi+=x;tree[rt].ma+=x;return;}PushDown(rt);int mid=(tree[rt].left+tree[rt].right)>>1;if(L<=mid) UpdateAdd(rt<<1,L,R,x);if(R>mid) UpdateAdd(rt<<1|1,L,R,x);PushUp(rt); }void Display(int rt){cout<<"-------------"<<endl;cout<<"id: "<<rt<<endl;cout<<"["<<tree[rt].left<<","<<tree[rt].right<<"]"<<endl;cout<<"mi: "<<tree[rt].mi<<endl;cout<<"ma: "<<tree[rt].ma<<endl;cout<<"sum: "<<tree[rt].sum<<endl;cout<<"add: "<<tree[rt].add<<endl;cout<<"set: "<<tree[rt].set<<endl; }void bfs(int rt){queue<int> q;while(!q.empty()) q.pop();q.push(rt);while(!q.empty()){int fst=q.front();q.pop();Display(fst);if(tree[fst].right>tree[fst].left){q.push(fst<<1);q.push(fst<<1|1);}} }void UpdateSet(int rt,int L,int R,int x){//把區(qū)間[x,y]置為xif(L<=tree[rt].left&&tree[rt].right<=R){tree[rt].set=x;tree[rt].sum=(LL)x*(tree[rt].right-tree[rt].left+1);tree[rt].mi=x;tree[rt].ma=x;tree[rt].add=0;return;}PushDown(rt);int mid=(tree[rt].left+tree[rt].right)>>1;if(L<=mid) UpdateSet(rt<<1,L,R,x);if(R>mid){UpdateSet(rt<<1|1,L,R,x);}PushUp(rt); }int main(){int n,m;//n個數(shù) m次詢問while(scanf("%d%d",&n,&m)!=EOF){for(int i=1;i<=n;i++) scanf("%lld",&a[i]);Build(1,1,n);//建立線段樹int op,x,y,z;for(int i=1;i<=m;i++){scanf("%d%d%d",&op,&x,&y);if(op==1){//詢問[x,y]的和，除以總數(shù)的平均 // printf("Case #%d:\n",i);printf("%.2lf\n",QuerySum(1,x,y) * 1.0 / (y - x + 1));}else if(op==2){//詢問[x,y]的最大值printf("Case #%d:\n",i);printf("%lld\n",QueryMax(1,x,y));}else if(op==3){//詢問[x,y]的最小值printf("Case #%d:\n",i);printf("%lld\n",QueryMin(1,x,y));}else if(op==0){//在[x,y]區(qū)間加上zscanf("%d",&z);UpdateAdd(1,x,y,z);}else{//把[x,y]置為zscanf("%d",&z);UpdateSet(1,x,y,z);}}}return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/zhumengdexiaobai/p/9540672.html

總結(jié)

以上是生活随笔為你收集整理的87-区间线段树（板子）--那个苑区的人最瘦的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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