HDU1754

hdu1754.cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define sd(x) scanf("%d",&x)
#define sdd(x,y) scanf("%d%d",&x,&y)
#define sddd(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a<b?a:b)
using namespace std;

const int N = 200000+5;

struct node
{
    int left,right,highest;
} tree[3*N];

void update_score(int i,int id,int score)
{
    int mid;
    if (tree[i].highest < score) tree[i].highest=score;
    if (tree[i].right-tree[i].left==1)
    {
        tree[i].highest=score;
        return;
    }

    mid = (tree[i].left+tree[i].right)/2;
    if (mid<=id-1) return update_score(i*2+1,id,score);
    else if (mid>=id) return update_score(2*i,id,score);
}

int  query_highest(int i,int l,int r)
{
    if (tree[i].left==l && tree[i].right==r) return tree[i].highest;
    int mid = (tree[i].left+tree[i].right)/2;
    if (mid<=l) return query_highest(2*i+1,l,r);
    else if (mid >=r) return query_highest(2*i,l,r);
    else
    {
        int maxl=query_highest(2*i,l,mid);
        int maxr=query_highest(2*i+1,mid,r);
        return MAX(maxl,maxr);
    }
}

void build(int i,int l,int r)
{
    tree[i].highest = 0;
    tree[i].left=l;
    tree[i].right=r;
    if (tree[i].right-tree[i].left==1) return;
    int mid = (l+r)/2;
    build(2*i,l,mid);
    build(2*i+1,mid,r);
}

int main()
{
  //  freopen("in.txt","r",stdin);
  //  freopen("out.txt","w",stdout);
    int n,m,tmp;
    char op;
    int a,b;
    while(~sdd(n,m))
    {
        build(1,0,n);
        for (int i=1;i<=n;i++)
        {
            sd(tmp);
            update_score(1,i,tmp);
        }
        for (int i=0;i<m;i++)
        {
            getchar();
            scanf("%c",&op);
            sdd(a,b);
            if (op=='Q') printf("%d\n",query_highest(1,a-1,b));
            else if (op=='U')
            {
                update_score(1,a,b);
            }
        }
    }
    return 0;
}