B - I Hate It (선분 트 리, 점 의 갱신 + 구간 최대 치)

             。        ，        ，        。 
         。 

       ，        ，         ，     ，       。  ，                。
Input
         ，        。 
         ，       N   M ( 0<N<=200000,05000 )，               。 
  ID     1  N。 
     N   ，   N        ，   i    ID i      。 
    M 。         C (  'Q' 'U') ，      A，B。 
 C 'Q'   ，          ，   ID A B(  A,B)     ，        。 
 C 'U'   ，          ，   ID A         B。 
Output
         ，           。
Sample Input
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
Sample Output
5
6
5
9




Hint
Huge input,the C function scanf() will work better than cin

#include
#include
#include
#define N 200009
using namespace std;

struct node
{
    int s,e;
    int p;
} dis[N*3+10];

int a[N];
void build(int num,int s,int e)//  
{
    dis[num].s=s;
    dis[num].e=e;
    if(s==e)
    {
        dis[num].p=a[s];
        return ;
    }
    int mid=(s+e)/2;
    build(num<<1,s,mid);
    build(num<<1|1,mid+1,e);
    dis[num].p=max(dis[num<<1].p,dis[num<<1|1].p);//     
}
void update(int num,int k,int pp)//      
{
    if(dis[num].s==dis[num].e)
    {
        if(dis[num].s==k)
            dis[num].p=max(dis[num].p,pp);
        return ;
    }
    int mid=(dis[num].s+dis[num].e)/2;
    if(mid1|1,k,pp);
    else update(num<<1,k,pp);
    dis[num].p=max(dis[num].p,max(dis[num<<1].p,dis[num<<1|1].p));
}
int query(int num,int s,int e)
{
    if(dis[num].e<=e&&dis[num].s>=s) return dis[num].p;
    int mid=(dis[num].s+dis[num].e)/2;
    int max_=0;
    if(mid>=s) max_=max(max_,query(num<<1,s,e));
    if(mid1|1,s,e));
    return max_;
}
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        memset(a,0,sizeof(a));
        for(int i=1; i<=n; i++)
            scanf("%d",&a[i]);
        build(1,1,n);
        char b[2];
        int x,y;
        while(m--)
        {
            scanf("%s%d%d",b,&x,&y);
            if(b[0]=='Q')
                printf("%d
",query(1,x,y));
            else
                update(1,x,y);
        }
    }
    return 0;
}