hdu 1754 I hate it

题目意思：

很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。
这让很多学生很反感。

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

当C为'Q'的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。
当C为'U'的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。

 

解题思路：

线段树，开始由于少了个等号，害我超时了至少20次，当时自己都快疯掉了，真的很想放弃了。每次tle都鼓励自己不要放弃，继续去查找错误。终于找到了，Happying！

code：

 

#include<stdio.h>
#include<string.h>

const int size=200005;

typedef struct d
{
  int max;
  int left;
  int right;
}d;

d tree[size*3+1];
int da[size];

int create(int p,int l,int r)
{
   int m,a1,a2;
   if(l>r) return 0; ////////////

   tree[p].left=l;tree[p].right=r;
   if(l==r)
   {
   tree[p].max=da[l];
   return tree[p].max;
   }
   m=(l+r)>>1;
   int t=p<<1;
   a1=create(t,l,m);
   a2=create(t+1,m+1,r);
   if(a1>a2)
   tree[p].max=a1;
   else tree[p].max=a2;
   return tree[p].max;
}
//不用每次都更新 一次create就可以了


/*
void create(int p,int l,int r)
{
   int m;
   tree[p].left=l;tree[p].right=r;
   //tree[p].col=-1;

   if(l==r) return;
   m=(l+r)/2;
   create(p*2,l,m);
   create(p*2+1,m+1,r);
}
*/
int query(int p,int l,int r)
{
    int m,a1,a2;
   if(l==r)
   return da[l];
   
   if(tree[p].left==l&&tree[p].right==r)
   return tree[p].max;

   //m=(l+r)>>1;

   m=(tree[p].left+tree[p].right)>>1;////////

   int t=p<<1;
   //if(r
   if(r<=m) return query(t,l,r); /////////

   
   if(l>m) return query(t+1,l,r);
   else
   {
   a1=query(t,l,m);
   a2=query(t+1,m+1,r);
   //return a1>a2?a1:a2;

   if(a1>a2) return a1;
   else return a2;
   }
}

void update(int p,int l,int r,int x)
{
     int m;

   if(tree[p].left==tree[p].right)
   {if(tree[p].max<x) tree[p].max=x;return ;}

   if(tree[p].max<x) tree[p].max=x;
   int t=p<<1;
   m=(tree[p].left+tree[p].right)>>1;
   if(r<=m) {update(t,l,r,x);return ;}
   if(l>m) {update(t+1,l,r,x);return ;}
   update(t,l,m,x);
   update(t+1,m+1,r,x);
}

int main()
{
  int n,m,x,y,i,temp;
  char ch[5];
  //create(1,0,200000);

  while(scanf("%d%d",&n,&m)!=EOF)
  {
  
  //for(i=1;i<=n;i++)

  //{scanf("%d",&da[i]);update(1,i,i,da[i]);}

  for(i=1;i<=n;i++)
  scanf("%d",&da[i]);
  create(1,1,n);
  while(m--)
  {
  scanf("%s%d%d",ch,&x,&y);
  //printf("%s %d %d\n",ch,x,y);

  if(*ch=='Q')
  {
      if(x==y){printf("%d\n",da[x]);continue;}
      if(x>y) {temp=x;x=y;y=temp;}
  printf("%d\n",query(1,x,y));
  }
  else if(*ch=='U')
  {update(1,x,x,y);da[x]=y;}
  }
  }
}