B - I Hate It

A comparative habit is popular in many schools. Teachers like to ask, from so and so to so and so, what is the highest score.
Many students are disgusted by this.

Like it or not, what you need to do now is to write a program to simulate the teacher's inquiry according to the teacher's requirements. Of course, teachers sometimes need to update a student's grades.

Input

This topic contains more than one set of tests. Please process until the end of the document.
In the first line of each test, there are two positive integers N and m (0 < N < = 200000, 0 < m < 5000), representing the number of students and the number of operations respectively.
Student ID numbers range from 1 to N.
The second line contains N integers representing the initial scores of these N students, where the number i represents the scores of the students with ID i.
Then there's line M. Each line has A character C (only 'Q' or 'U') and two positive integers A and B.
When C is' Q ', it means that this is A query operation. It asks the students whose ID is from A to B (including A and b), what is the highest score.
When C is' U ', it means that this is an update operation, which requires changing the score of the student with ID A to B.

Output

For each query operation, output the highest score in one line.

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

It's a line segment number board sub problem, but there are a lot of places to update. The maximum value of the parent node represents the maximum value of the child nodes within the scope of the parent node. Every time you change the value of a certain number, you need to update the maximum value of the parent node above the number, and nothing else. The board is gradually familiar with the data structure

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<queue>
using namespace std;
int v[200200];
char s[5];
int z=0;
struct uuu
{
    int l,r,mid,maxx;  // Left and right sides and middle value of record number
}segtree[800008];
int  build(int l,int r,int index)
{
    segtree[index].r=r,segtree[index].l=l;
    segtree[index].mid=(r+l)/2;
    if(r==l)
    {
        segtree[index].maxx=v[l];
        return segtree[index].maxx;
    }
    segtree[index].maxx=max(build(l,segtree[index].mid,index*2),build(segtree[index].mid+1,r,index*2+1));
    return segtree[index].maxx;
}
void update(int i,int j,int index)
{
    if(segtree[index].l==i&&segtree[index].r==i)
    {
        segtree[index].maxx=j;
        return ;
    }
    if(i<=segtree[index].mid)
    {
        update(i,j,index*2);
    }
    else
    {
        update(i,j,index*2+1);
    }
    segtree[index].maxx=max(segtree[index*2].maxx,segtree[index*2+1].maxx);
}
int query(int l,int r,int index)
{
    if(segtree[index].l==l&&segtree[index].r==r)
    {
     return segtree[index].maxx;
    }
    else if(l>segtree[index].mid)
    {
       return query(l,r,index*2+1);
    }
    else if(r<=segtree[index].mid)
    {
       return query(l,r,index*2);
    }
    else
    {
        return max(query(l,segtree[index].mid,index*2),query(segtree[index].mid+1,r,index*2+1));
    }
}
int main()
{
    int m,n;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        for(int a=1;a<=m;a++)
        {
            scanf("%d",&v[a]);
        }
         build(1,m,1);
        while(n--)
        {
            int i,j;
            scanf("%s",s);
            scanf("%d%d",&i,&j);
            if(s[0]=='Q')
            {
                printf("%d\n",query(i,j,1));
            }
            else
            {
                update(i,j,1);
            }
        }
    }
    return 0;
}