当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

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

发表于: 2012-10-21   作者:暴风雪   来源:转载   浏览次数:
摘要: 大致题意:     给出一个数组,在线更新点的值,查询区间的极值。   大致思路:     简单线段树。   #include<iostream> #include<cstring> #include<cstdio> using namespace std; const int Ma

大致题意:

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

 

大致思路:

    简单线段树。

 

#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;
}

 

 

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

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
参考资料: http://www.cppblog.com/MiYu/archive/2010/08/29/125199.html 此题的simple建立的树为: A
线段树需要的空间。 区间为1-->n 假设是一棵完全二叉树,且树高为i。 完全二叉树性质:第i层最多
Buy Tickets Time Limit: 4000MS Memory Limit: 65536K Total Submissions: 12930 Accepted: 6412 D
先看网上的介绍: 线段树也叫区间树,顾名思义,线段树是一种基于区间的树,每个节点表示一个“线段
Buy Tickets Time Limit: 4000MS Memory Limit: 65536K Total Submissions: 11102 Accepted: 5417 D
题意: 同上 题解: 抓着这题作死的搞~~是因为今天练习赛的一道题.SPOJ KQUERY.直到我用最后一种树状
KIDx的解题报告 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4027 加了输入外挂之后,排
Mayor's posters Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 40494 Accepted: 11
成段更新,需要用到延迟标记(或者说懒惰标记),简单来说就是每次更新的时候不要更新到底,用延迟标记使
线段树在一些acm题目中经常见到,这种数据结构主要应用在计算几何和地理信息系统中。下图就为一个线
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号