简单线段树
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int maxn=200000+100; struct settree { int val; }tree[maxn*3]; int aa[maxn]; int n,m; void build(int root,int aa[],int l,int r) { if(l==r) tree[root].val=aa[l]; else { int mid=(l+r)/2; build(root*2,aa,l,mid); build(root*2+1,aa,mid+1,r); tree[root].val=max(tree[root*2].val,tree[root*2+1].val); } } void upone(int root,int l,int r,int v,int vval) { if(l==r) { if(l==v) tree[root].val=vval; return; } int mid=(l+r)/2; if(v<=mid) upone(root*2,l,mid,v,vval); else upone(root*2+1,mid+1,r,v,vval); tree[root].val=max(tree[root*2].val,tree[root*2+1].val); } int serch(int root,int l,int r,int a,int b) { if(b<l||a>r) return 0; if(a<=l&&r<=b) return tree[root].val; int mid=(l+r)/2; int mm=max(serch(root*2,l,mid,a,b),serch(root*2+1,mid+1,r,a,b)); return mm; } int main() { while(~scanf("%d%d",&n,&m)) { for(int i=1;i<=n;i++) scanf("%d",&aa[i]); build(1,aa,1,n); char cc; int a,b; getchar(); for(int i=0;i<m;i++) { scanf("%c %d %d",&cc,&a,&b); getchar(); if(cc=='Q') { int mm=serch(1,1,n,a,b); printf("%d\n",mm); } else if(cc=='U') { upone(1,1,n,a,b); } } } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/7265071.html
相关资源：数据结构—成绩单生成器