原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1754
线段树的模板题，详细的都写在代码里了
//不知道为什么定义单个字符，用%c输入会超时，换成字符数组和%s就过了
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue> #include <cmath> #define ll long long #define pi 3.1415927 using namespace std; int tree[400005],num[200005]; void build(int i ,int j, int k) { //建树，将1-n 2分分配给子节点，最后在给最终的节点赋值 if(j==k) { tree[i]=num[j]; return ; } int mid =(j+k)>>1; build(i<<1,j,mid); build(i<<1|1,mid+1,k); tree[i]=max(tree[i<<1],tree[i<<1|1]); } void add(int i,int x, int j ,int k,int p) { //维护 从头寻找要改变的节点，找到后再依次返回父节点进行维护 if (j==k) { tree[i]=p; return ; } int mid =(j+k)>>1; if(x<=mid) add(i<<1,x,j,mid,p); else add(i<<1|1,x,mid+1,k,p); tree[i]=max(tree[i<<1],tree[i<<1|1]); } int finds(int i,int x, int y, int j, int k) { //查询 寻找符合要求的节点 if(x<=j && y>=k) return tree[i]; int mid=(j+k)>>1; if(y<=mid) return finds(i<<1,x,y,j,mid); else if(x>mid) return finds(i<<1|1,x,y,mid+1,k); else return max(finds(i<<1,x,y,j,mid),finds(i<<1|1,x,y,mid+1,k)); } int main () { int n,m,i,t,j,k,x,y; char str[3]; //这里不用字符数组不知道为什么莫名其妙的超时 while(scanf("%d %d",&n,&m)!=EOF) { for(i=1;i<=n;++i) scanf("%d",&num[i]); build(1,1,n); while(m--) { scanf("%s %d %d",str,&x,&y); if(str[0]=='Q'){ t=finds(1,x,y,1,n); printf("%d ",t); } else if (str[0]=='U') add(1,x,1,n,y); } } return 0; }