hdu1754 I Hate It(学写线段树)

题目：

题目是中文的，就不解释了。。大致思路：建一根线段树，每个结点，记录该结点区间的最大值。。这样查询起来比较好。。但仍耗时将近2000MS。。

my code:

 

#include<iostream>
#define maxsize 200000
using namespace std;

struct node
{
    int max;
    int left;
    int right;
};

int N,M,data[maxsize+5];
node tree[maxsize*3+5];

int max(int a,int b)
{return a>b?a:b;}

int maketree(int p,int i,int j)//建树
{
    int m,n;
    tree[p].left=i;
    tree[p].right=j;
    if(i==j) {tree[p].max=data[i];return data[i];}
    m=(i+j)>>1;n=p<<1;
    tree[p].max=max(maketree(n,i,m),maketree(n+1,m+1,j));
    return tree[p].max;
}
void update(int p,int i,int t)//更新
{
    int m,n;
    if(tree[p].max<t) tree[p].max=t;
    if(tree[p].left==tree[p].right) return ;
    m=(tree[p].left+tree[p].right)>>1;n=p<<1;
    if(i<=m) {update(n,i,t);return;}
    if(i>m) {update(n+1,i,t);return;}
}
int query(int p,int i,int j)//查询
{
    int m,n;
    if(tree[p].left==i&&tree[p].right==j) return tree[p].max;
    m=(tree[p].left+tree[p].right)>>1;n=p<<1;
    if(j<=m) return query(n,i,j);
    if(i>m) return query(n+1,i,j);
    return max(query(n,i,m),query(n+1,m+1,j));
}
int main()
{
    int i,j;
    char order;
    while(cin>>N>>M)
    {
        for(i=1;i<=N;i++)
            scanf("%d",data+i);
        maketree(1,1,N);
        while(M--)
        {
            getchar();
            scanf("%c%d%d",&order,&i,&j);
            if(order=='Q')
            {
                if(i>j){i^=j;j^=i;i^=j;}
                cout<<query(1,i,j)<<endl;
                continue;
            }
            update(1,i,j);
            data[i]=j;
        }
    }
    return 0;
}

看到后面很多大牛的代码耗时只有不到300MS，不知道是怎么写的，效率如此高。。有机会弄过来观摩下。。。