本文共 2150 字,大约阅读时间需要 7 分钟。
5
6
5
9
单点更新,最大值
#include#include #include #include #include using namespace std;const int MAXN = 200000+5;int n,m;int tree[MAXN<<2];int add[MAXN<<2];int a[MAXN];char c[5];void build(int p, int l, int r) { if(l == r){ tree[p] = a[l]; return ; } int m = (l+r)>>1; build(p<<1,l,m); build(p<<1|1,m+1,r); tree[p] = max(tree[p<<1],tree[p<<1|1]); }void updateOne(int p, int l, int r, int ind,int x) { if(l == r){ tree[p] = x; //这里是tree[p] 不是tree[l] return; } int m = (l+r)>>1; if(ind <= m) updateOne(p<<1,l,m,ind,x); else updateOne(p<<1|1,m+1,r,ind,x); tree[p] = max(tree[p<<1],tree[p<<1|1]); } int query(int p, int l, int r, int tl, int tr) { if(l >= tl && r <= tr){ return tree[p]; } int m = (l+r)>>1; int ans = 0; if(tl <= m) ans = max(query(p<<1,l,m,tl,tr),ans); if(tr > m) ans = max(query(p<<1|1,m+1,r,tl,tr),ans); return ans; }int main() { // freopen("C:/Users/zhangwei/Desktop/input.txt","r",stdin); while(scanf("%d%d",&n,&m) != EOF){ memset(a,0,sizeof(a)); memset(tree,0,sizeof(tree)); for(int i = 1; i <= n; ++i){ scanf("%d",&a[i]); } build(1,1,n);// int ans = query(1,1,n,1,n);// printf("%d\n",ans); while(m--){ scanf("%s",c); int a,b; scanf("%d%d",&a,&b); //printf("%s %d %d\n",c,a,b); if(c[0] == 'Q'){ int ans = query(1,1,n,a,b); printf("%d\n",ans); } else if(c[0] == 'U'){ updateOne(1,1,n,a,b); } } } return 0; }
转载地址:http://erimi.baihongyu.com/