HDU 1754 I Hate It 基础线段树

用区间值m表示这段区间的最大值，一直更新这个区间的最大值，很基础的线段树

#include<iostream>
#include<stdio.h>
using namespace std;
#define N 200005
struct node{
    int l,r,m;
}tree[N*4];
int a[N];
void build(int left,int right,int i){
    tree[i].l=left;
    tree[i].r=right;
    if(tree[i].l==tree[i].r){
        tree[i].m=a[tree[i].l];
        return ;
    }
    int mid=(tree[i].l+tree[i].r)>>1;
    build(left,mid,i*2);
    build(mid+1,right,i*2+1);
    tree[i].m=max(tree[i*2].m,tree[i*2+1].m);
}
void updata(int left,int right,int i,int val){
 //   cout<<tree[i].l<<" "<<tree[i].r<<endl;
    if(left==tree[i].l&&right==tree[i].r){
        tree[i].m=val;
        return ;
    }
     if(tree[i].l>left || tree[i].r<left) return ;
    int mid=(tree[i].r+tree[i].l)>>1;
    updata(left,right,i*2,val);
    updata(left,right,i*2+1,val);
    tree[i].m=max(tree[i*2].m,tree[i*2+1].m);
}
int ans=0;
void query(int left,int right,int i){
 //   cout<<"Q 4 5 "<<left<<" "<<right<<" "<<tree[3].m<<endl;
    if(tree[i].l==left&&tree[i].r==right){
        if(tree[i].m>ans)
            ans=tree[i].m;
        return ;
    }
    int mid=(tree[i].l+tree[i].r)>>1;
    if(mid>=right)
        query(left,right,i*2);
    else if(mid<left)
        query(left,right,i*2+1);
    else{
        query(left,mid,i*2);
        query(mid+1,right,i*2+1);
    }

}
int main(){
//    freopen("in.txt","r",stdin);
    int m,n,x,y;
    char t[5];
    while(~scanf("%d%d",&n,&m)){
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        build(1,n,1);
        while(m--){
            scanf("%s %d%d",t,&x,&y);
//            cout<<t<<" "<<x<<" "<<y<<endl;
            if(t[0]=='Q'){
                ans=0;
                query(x,y,1);
                printf("%d\n",ans);
            }
            else{
                updata(x,x,1,y);
            }
        }
    }
}

HDU 1754 I Hate It 基础线段树,布布扣,bubuko.com

HDU 1754 I Hate It 基础线段树

原文：http://blog.csdn.net/youngyangyang04/article/details/38141383