HDU - 1754 I Hate It

题意：中文题，

思路：线段树的节点更新，储存区间的最大值

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 20010;

int tree[MAXN<<1+10];

void build_tree(int l,int r,int root){
    if (l == r){
        scanf("%d",&tree[root]);
         return;
    }
    int m = (l+r) >> 1;
    build_tree(l,m,root<<1);
    build_tree(m+1,r,root<<1|1);
    tree[root] = max(tree[root<<1],tree[root<<1|1]);
}

void update(int pos,int date,int l,int r,int root){
    if (l == r){
        tree[root] = date;
        return;
    }
    int m = (l+r) >> 1;
    if (pos <= m)
        update(pos,date,l,m,root<<1);
    else update(pos,date,m+1,r,root<<1|1); 
    tree[root] = max(tree[root<<1],tree[root<<1|1]);
}

int query(int L,int R,int l,int r,int root){
    int sum = -11111111;
    if (L <= l && r <= R)
        return tree[root];
    int m = (l+r) >> 1;
    if (L <= m)
        sum = max(sum,query(L,R,l,m,root<<1));
    if (R > m)
        sum = max(sum,query(L,R,m+1,r,root<<1|1));
    return sum;
}

int main(){
    int num,que;
    char op;
    int a,b;
    while (scanf("%d%d",&num,&que) != EOF){
        build_tree(1,num,1);
        for (int i = 0; i < que; i++){
            scanf("%*c%c %d %d",&op,&a,&b);
            if (op == ‘U‘)
                update(a,b,1,num,1);
            else printf("%d\n",query(a,b,1,num,1));
        }
    }
    return 0;
}

HDU - 1754 I Hate It,布布扣,bubuko.com

HDU - 1754 I Hate It

原文：http://blog.csdn.net/u011345136/article/details/20557105