简单线段树
#include<stdio.h> #define N 200002 int start,end,a[N]; struct tree { int left,right,maxnum; }p[N*3]; int max(int a,int b) { if(a>b)return a; return b; } void insert(int l,int r,int i) { p[i].left=l;p[i].right=r; if(l==r) { p[i].maxnum=a[l];return ; } int mind=(l+r)/2; insert(l,mind,i*2); insert(mind+1,r,i*2+1); p[i].maxnum=max(p[i*2].maxnum,p[i*2+1].maxnum); } int find(int l,int r,int i) { if(p[i].left==l&&p[i].right==r)return p[i].maxnum; int mind=(p[i].left+p[i].right)/2; if(l>mind) return find(l,r,i*2+1); else if(r<=mind) return find(l,r,i*2); else { int x,y; x=find(l,mind,i*2); y=find(mind+1,r,i*2+1); return max(x,y); } } void xiugai(int l,int r,int i) { if(l==r) { p[i].maxnum=end;return; } int mind=(l+r)/2; if(start<=mind) xiugai(l,mind,i*2); else xiugai(mind+1,r,i*2+1); p[i].maxnum=max(p[i*2].maxnum,p[i*2+1].maxnum); } int main() { int i,n,m; char ch; while(scanf("%d%d",&n,&m)!=EOF) { for(i=1;i<=n;i++) scanf("%d",&a[i]); insert(1,n,1); getchar(); for(i=0;i<m;i++) { scanf("%c%d%d",&ch,&start,&end); getchar(); if(ch=='Q') printf("%d\n",find(start,end,1)); else xiugai(1,n,1); } } return 0; }