`
暴风雪
  • 浏览: 388027 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
社区版块
存档分类
最新评论

[线段树,单点更新]hdoj 1754:I Hate It

阅读更多

大致题意:

    给出一个数组,在线更新点的值,查询区间的极值。

 

大致思路:

    简单线段树。

 

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int Max = 250005;

struct data{
    int l, r, num;
}node[4*Max];     //  线段树节点的数据结构。
int num[Max];

void BuildTree(int left, int right, int u){      //  建树。
    node[u].l = left;
    node[u].r = right;
    if(left == right)
        node[u].num = num[left];
    else{
        BuildTree(left, (left+right)/2, 2*u);
        BuildTree((left+right)/2+1, right, 2*u+1);
        node[u].num = max(node[2*u].num , node[2*u+1].num);
    }
}

int updata(int loc, int w, int u){              //  修改。
    if(node[u].l == node[u].r ){
        node[u].num = w;
        return 0;
    }
    if(loc <= node[2*u].r){
        updata(loc , w, u*2);
    }else{
        updata(loc , w, u*2+1);
    }
    node[u].num = max(node[2*u].num , node[2*u+1].num);
    return 0;
}

int query(int left, int right, int u){           //  查询。
    if(node[u].l == left && node[u].r == right)
        return node[u].num;
    if(right <= node[2*u].r)
        return query(left, right, 2*u);
    if(left >= node[2*u+1].l)
        return query(left, right, 2*u+1);
    int a = query(left, (node[u].l+node[u].r)/2, 2*u);
    int b = query((node[u].l+node[u].r)/2+1, right, 2*u+1);
    return max(a,b);
}

int main()
{
    char str[10];
    int cas,i,j,a,b,c,n,m,t=0;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d",&num[i]);
        } 
        BuildTree(1,n,1);
        while(m--)
        {
            scanf("%s",str);
            scanf("%d%d",&a,&b);
            if(str[0]=='Q'){
                a=query(a,b,1);
                printf("%d\n",a);
            }
            if(str[0]=='U'){
                updata(a,b,1);
            }
        }
    }
    return 0;
}

 

 

2
2
分享到:
评论
1 楼 Wangshufeng3 2012-11-11  
请教大神:

5 6
1 2 3 4 5
Q 1 5   ===>  5
如果
U 5 3
Q 1 5   ===>  5 or 4  ??????/

谢谢

相关推荐

    acm线段树基本

    ACM线段树基本 线段树是一种常用的数据结构,广泛应用于算法竞赛编程和数据结构设计中。它是一种树形结构,能够高效地进行区间查询和修改操作。 线段树的基本概念 线段树是一棵二叉树,每个结点表示一个区间。...

    线段树总结

    例如,在HDOJ 1754题目的场景下,我们可以用线段树维护区间内的最大值或最小值,只需在节点中存储区间内的最大值或最小值,而非累计和。 7. **优化**: 在处理大规模数据时,为了提高效率,可以采用懒惰更新策略。...

    HDOJ题目分类 HDOJ题目分类

    【标题】:“HDOJ题目分类 HDOJ题目分类” HDOJ,全称为Happy DingO Online Judge,是一个在线编程竞赛平台,它为参赛者提供了大量编程题目进行练习和比赛,旨在提升编程技能和算法理解。HDOJ的题目分类是帮助用户...

    hdoj2066最短路

    根据给定的文件信息,我们可以总结出以下关于“hdoj2066最短路径”的相关知识点: ## hdoj2066最短路径概述 ### 标题解析:“hdoj2066最短路” - **hdoj**:High Density Online Judge(高密度在线评测系统),是...

    hdoj--acm题目,有注释

    "hdoj--acm题目,有注释" 本资源提供了多个 ACM 题目的解决方案,代码都带有注释,非常适合初学者学习。下面是对每个题目的知识点总结: 2000:本题目要求输入三个字符,输出按照从小到大排序的结果。本代码使用了...

    hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000

    【标题】"hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000" 涉及的知识点主要围绕着“杭电在线判题系统(HDOJ)”以及其中的题目1082和10系列题目。HDOJ是杭州电子科技大学主办的一个在线编程竞赛平台,...

    HDOJ 80题 Java

    【标题】"HDOJ 80题 Java"是一份专为Java程序员设计的在线编程挑战集合,源自杭州电子科技大学(HDOJ)的在线评测系统。这些题目旨在帮助Java开发者提升算法理解与编程能力,同时也为那些习惯于C++但希望在Java环境...

    HDOJ离线版

    《HDOJ离线版:探索编程竞赛的智慧宝库》 HDOJ,全称为“杭州电子科技大学在线评测系统”(Hangzhou Dianzi University Online Judge),是中国早期的编程竞赛平台之一,深受广大编程爱好者和在校学生的喜爱。HDOJ...

    HDOJ1002

    ACM ICPC HDOJ1002

    HDOJ1001

    ACM ICPC HDOJ1001

    ACM HDOJ 课件

    8. **计算几何**:计算几何涉及到几何对象的表示、操作和查询,如点、线段、圆等。在处理图形和空间问题时,计算几何提供了有效的算法,如最近点对查找、凸包计算等。 通过学习这些课件,参赛者可以系统地提升自己...

    HDOJ部分简单题(JAVA)

    HDOJ1000.java HDOJ1001.java HDOJ1089.java HDOJ1090.java HDOJ1091.java HDOJ1092.java HDOJ1093.java HDOJ1094.java HDOJ1095.java HDOJ1108.java HDOJ1406.java HDOJ2001.java HDOJ2002.java HDOJ2003.java HDOJ...

    hdoj1005 Number Sequence 代码

    ### hdoj1005 Number Sequence 代码分析与解析 #### 一、问题背景与题目概述 在深入了解代码之前,我们先来了解下题目背景。`hdoj1005 Number Sequence` 是杭州电子科技大学在线评测系统(Online Judge,简称OJ)...

    hdoj1001标程

    hdoj1001标程

    hdoj1004 解题代码 答案

    hdoj1004,解题代码,答案代码,欢迎下载

    HDOJ 1008

    ACM ICPC HDOJ1008

    HDOJ1003

    ACM ICPC HDOJ1003

    hdoj 2013 多校训练4标程+解题报告

    【标题解析】:“hdoj 2013 多校训练4标程+解题报告”这个标题表明,这是一个关于2013年Happy Dream Online Judge(简称hdoj)组织的多校联合编程训练的资料。"4标程"意味着包含了四道题目(或者可能是四个阶段)的...

    HDOJ.rar_HD_HDOJ

    【标题】"HDOJ.rar_HD_HDOJ" 是一个与HDU(杭州电子科技大学)在线判题系统HDOJ相关的压缩包文件,其中包含了大量编程题目的源代码。 【描述】提到,这个压缩包包含了几百道HDOJ题目的源代码,这意味着它是一个宝贵...

    OJ.tar.gz_HDOJ _OJ源码_oj

    【OJ.tar.gz_HDOJ _OJ源码_oj】是一个包含编程竞赛平台HDOJ(Happy Ding Octopus Judge)部分源代码的压缩文件。这个压缩包的主要目的是供学习和研究使用,尤其是针对50至60题目的解题算法和系统实现。通过分析这些...

Global site tag (gtag.js) - Google Analytics