#线段树#JZOJ 1959 最大值

本文主要是介绍#线段树#JZOJ 1959 最大值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

线段树

#include <cstdio>
#include <cctype>
#include <climits>
#include <algorithm>
using namespace std;
struct node{int w;}tree[400001]; int a[100001],n,m,ans;
inline int in(){int ans=0,f=1; char c=getchar();while (!isdigit(c)&&c!='-') c=getchar();if (c=='-') c=getchar(),f=-f;while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans*f;
}
int build(int l,int r,int k){if (l==r) return tree[k].w=a[r];return tree[k].w=max(build(l,(l+r)>>1,k<<1),build(((l+r)>>1)+1,r,(k<<1)+1));
}
inline void in1(int &x,int &y){x=in(); y=in();}
void update(int l,int r,int x,int y,int k){if (x==l&&x==r) {tree[k].w=y; return;}int mid=(l+r)>>1;if (x<=mid) update(l,mid,x,y,k<<1);else update(mid+1,r,x,y,(k<<1)+1);tree[k].w=max(tree[k<<1].w,tree[(k<<1)+1].w);
}
void find(int l,int r,int x,int y,int k){if (x==l&&y==r) {ans=max(ans,tree[k].w); return;}int mid=(l+r)>>1;if (y<=mid) find(l,mid,x,y,k<<1);//左边else if (x>mid) find(mid+1,r,x,y,(k<<1)+1);//右边else find(l,mid,x,mid,k<<1),find(mid+1,r,mid+1,y,(k<<1)+1);//一起搜
}
int main(){n=in();for (int i=1;i<=n;i++) a[i]=in();build(1,n,1); m=in();while (m--){int q=in(),x,y; ans=INT_MIN; in1(x,y);if (q==1) update(1,n,x,y,1);else find(1,n,x,y,1),printf("%d\n",ans);}return 0;
}

这篇关于#线段树#JZOJ 1959 最大值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---