HDU 1754

• 求区间最值.线段树维护

  #include <iostream>
  #include <string.h>
  
  using namespace std;
  const int maxn = 2e5+5;
  struct segementTree{
  	int left,right;
  	int div;
  } e[4*maxn];
  int a[maxn];
  int n,m;
  
  void build(int p,int left,int right) {
  	e[p].left = left; e[p].right = right;
  	if (left == right) {
  		e[p].div = a[left]; return ;
  	}
  	int mid = (left + right)/2;
  	build(2*p,left,mid);
  	build(2*p+1,mid+1,right);
  	e[p].div = max(e[p*2].div,e[p*2+1].div);
  }
  
  void change(int p,int index,int val) {
  	if (e[p].left == e[p].right) {
  		e[p].div = val;
  		return ;
  	}
  	int mid = (e[p].left + e[p].right)/2;
  	if (index <= mid) change(2*p,index,val);
  	else change(2*p+1,index,val);
  	e[p].div = max(e[p*2].div,e[p*2+1].div);
  }
  int ask(int p,int left,int right) {
  	if (left <= e[p].left && right >= e[p].right) return e[p].div;
  	int mid = (e[p].left + e[p].right)/2;
  	int val = -(1<<30);
  	if (left <= mid) val = max(ask(2*p,left,right),val);
  	if (right > mid) val = max(ask(2*p+1,left,right),val);
  	return val;
  }
  
  int main() {
  //	freopen("a.txt","r",stdin);
  	while (scanf("%d%d",&n,&m) != EOF) {
  		memset(a,0,sizeof a);
  		memset(e,0,sizeof e);
  		for (int i=1; i<=n; i++) scanf("%d",&a[i]);
  		build(1,1,n);
  		for (int i=1; i<=m; i++) {
  			char ch; int u,v;
  			scanf("\n%c %d %d",&ch,&u,&v);
  			if (ch == 'Q') printf("%d\n",ask(1,u,v));
  			else change(1,u,v);
  		}
  		
  	}
  	return 0;
  }