哪些做图片赚钱的网站/奉化seo页面优化外包
题目
蒜头君有很多苹果,每个苹果都有对应的甜度值。
蒜头君现在想快速知道从第 i 个苹果到第 j 个苹果中,最甜的甜度值是多少。
因为存放时间久了,有的苹果会变甜,有的苹果会因为腐烂而变得不甜,所以蒜头君有时候还需要修改第 i 个苹果的甜度值
分析
把区间和改为区间最大值即可
代码
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 200010;
int s[4*MAX_N];
void up(int p)
{s[p] =max(s[p*2],s[p*2+1]);
}
void modify(int p,int l,int r,int x,int v)
{if(l==r){s[p]=v;return ;}int mid=(l+r)/2;if(x<=mid){modify(p*2,l,mid,x,v);}else{modify(p*2+1,mid+1,r,x,v);}up(p);
}
int query(int p,int l,int r,int x,int y)
{if(x<=l&&r<=y){return s[p];}int mid=(l+r)/2,res=0;if(x<=mid){res=max(res,query(p*2,l,mid,x,y));}if(y>mid){res=max(res,query(p*2+1,mid+1,r,x,y));}return res;
}
int main() {int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;++i){int d;scanf("%d",&d);modify(1,1,n,i,d);}getchar();char op;while(m--){cin>>op;int i,j;scanf("%d%d",&i,&j);if(op=='U')modify(1,1,n,i,j);elseprintf("%d\n",query(1,1,n,i,j));}return 0;
}