HDOJ1754（线段树or树状数组）

69 阅读 0 评论 46 点赞

我是靠谱客的博主落后金毛，最近开发中收集的这篇文章主要介绍HDOJ1754（线段树or树状数组），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

本文提供两种做法：

线段树
树状数组

线段树做法-单点更新

注意事项：

1.尽量别用cin这种输入，容易超时。

2.尽量少使用三目运算，例如HDOJ1754，如果使用if判断句，则AC，用三目运算，就超时了。

    /* 
    HDOJ1754 
    作者：陈佳润 
    时间：2013-03-29 
    */  
    #include<stdio.h>  
       
    #define MaxSize 200001  
    //#define max(a,b) (a>b?a:b)  
    int Tree[MaxSize*4];  
       
    int max(int a,int b){  
        if(a>b)  
            return a;  
        return b;  
    }  
    void Create(int p,int l,int r){//可存在[a,a]的节点  
        if(l==r){//当达到叶子节点时  
            scanf("%d",&Tree[p]);  
            return;  
        }  
        int mid=(l+r)>>1;//计算中间值  
        Create(p<<1,l,mid);//向左递归  
        Create(p<<1|1,mid+1,r);//向右递归  
        Tree[p]=max(Tree[p<<1],Tree[p<<1|1]);//计算节点值  
    }  
    void Add(int i,int add,int p,int l,int r){//增加叶子节点数值  
        if(l==r){//当达到叶子节点时，加上修改值  
            Tree[p]=add;  
            return ;  
        }  
        int mid=(l+r)>>1;//计算中间值  
        if(i<=mid)//向左递归  
            Add(i,add,p<<1,l,mid);  
        else//向右递归  
            Add(i,add,p<<1|1,mid+1,r);  
        Tree[p]=max(Tree[p<<1],Tree[p<<1|1]);//计算节点值  
    }  
    int Query(int p,int l,int r,int L,int R){  
        if(R>=r&&L<=l)//当查询的区间比树的区间大时  
            return Tree[p];  
        int sum=-1;//当前节点的值  
        int mid=(l+r)>>1;//计算中间值  
        if(L<=mid)//向左递归  
            sum=max(sum,Query(p<<1,l,mid,L,R));  
        if(R>mid)//向右递归  
            sum=max(sum,Query(p<<1|1,mid+1,r,L,R));  
        return sum;  
    }  
    int main()  
    {  
        int n,b,a,m,i;  
        char c;  
    //  freopen("1.txt","r",stdin);  
        while(scanf("%d%d",&n,&m)!=EOF){  
            Create(1,1,n);  
            for(i=1;i<=m;i++){  
                scanf("%*c%c %d %d",&c,&a,&b);  
                if(c=='Q')  
                    printf("%dn",Query(1,1,n,a,b));  
                if(c=='U')  
                    Add(a,b,1,1,n);  
            }  
        }  
        return 0;  
    }

树状数组做法

    /* 
    HDOJ1754 
    作者：陈佳润 
    2013-04-01 
    */  
    #include<iostream>  
    using namespace std;  
    #define max(a,b) (a>b?a:b)  
    int a[200001],c[200001],n;  
    int lowbit(int k){//返回二进制的k后面最大连续0的个数，包括第一个1  
        return -k&k;  
    }  
    void Create(){//建立树状数组  
        int i,j;  
        for(i=1;i<=n;i++){  
            c[i]=a[i];  
            for(j=i-1;j>i-lowbit(i);j--){//按控制范围计算  
                c[i]=max(c[i],a[j]);  
            }  
        }  
    }  
    void modify(int i,int data){//修改某个数  
        int j;  
        a[i]=data;//修改原本的数据  
        for(j=i;j<=n;j+=lowbit(j))//修改树状数组  
            c[j]=max(c[j],data);  
    }  
    int query(int l,int r){//查询  
        int ans=a[r];  
        while(1){  
            ans=max(ans,a[r]);//如果无法整个区间，就一个一个  
            if(r==l)break;//查询完毕  
            for(r=r-1;r-l>=lowbit(r);r-=lowbit(r))//大区间内查询  
                ans=max(ans,c[r]);  
        }  
        return ans;  
    }  
    int main()  
    {  
        int i,j,m;  
        char cc;  
    //  freopen("1.txt","r",stdin);  
        while(scanf("%d%d",&n,&m)!=EOF){  
            for(i=1;i<=n;i++)  
                scanf("%d",&a[i]);  
            Create();//建立树状数组  
            while(m--){  
                scanf("%*c%c %d %d",&cc,&i,&j);  
                if(cc=='Q')  
                    printf("%dn",query(i,j));  
                else  
                    modify(i,j);  
            }     
        }  
        return 0;  
    }