`

树状数组求区间最值 hdu 1754

    博客分类:
  • acm
阅读更多
原理:求和时c数组存的是相应区间的和,而在这c数组(mkx数组)求的是相应区间的最大值

#include <bits/stdc++.h>
using namespace std;
const int N = 400000+100;
int n,m,k,l,r;
int a[N];
int mkx[N],num[N];
char s[10];
int lowbit(int x)
{
    return x&(-x);
}
void init()
{
    for(int i=1;i<=n;i++)
    {
        mkx[i] = num[i];
        for(int j=1;j<lowbit(i);j*=2)
        {
           mkx[i] = max(mkx[i],mkx[i-j]);
        }
    }
    return ;
}
void update(int l,int val)
{
    num[l] = val;
    for(int i=l;i<=n;i+=lowbit(i))
    {
        mkx[i]=val;
        for(int j=1;j<lowbit(i);j*=2)
        {
            mkx[i] = max(mkx[i],mkx[i-j]);
        }
    }
    return ;
}
int query(int l,int r)
{
    int ans =  max(num[l],num[r]);
    while(true)
    {
        ans = max(ans, num[r]);
        if(l == r) break;
        r--;
        for(r;r-l>lowbit(r);r-=lowbit(r))
        {
            ans = max(ans,mkx[r]);
        }
    }
    return ans;
}
int main()
{
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        memset(num,0,sizeof(num));
        memset(mkx,0,sizeof(mkx));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&num[i]);
        }
        init();
        while(m--)
        {
            scanf("%s %d %d",s,&l,&r);
            if(s[0]=='U') update(l,r);
            else printf("%d\n",query(l,r));
        }
    }
    return 0;
}
 

分享到:
评论

相关推荐

    树状数组(Binary Indexed Tree)

    - **解法**:可以考虑使用树状数组来维护区间内的最值,通过低比特操作实现高效更新和查询。 7. **二维树状数组 POJ2155:Matrix** - **题意**:给定一个n*n的矩阵,支持对子矩阵进行翻转操作,并查询特定位置的...

    线段树入门学习(兼解HDU1754)

    HDU1754这道题目可能是要求在一个数组上执行一系列区间加法操作和区间查询操作。线段树可以很好地解决这类问题,通过一次预处理构建线段树,后续的修改和查询操作都能在较短的时间复杂度内完成,比直接遍历数组的...

    【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源

    【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源

    ACM hdu 线段树题目+源代码

    线段树是一种树形结构,它将一个数组分割成多个小 区间,每个区间对应树上的一个节点。线段树的每个节点都包含了该节点对应的区间信息。 线段树的主要应用 线段树的主要应用是解决区间问题,例如区间和、区间...

    hdu.rar_hdu

    3. **数据结构**:数组、链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)、图(邻接矩阵、邻接表、最小生成树、拓扑排序等)。 4. **字符串处理**:KMP算法、Manacher's Algorithm、Rabin-Karp算法等。 5. **...

    hdu1250高精度加法

    ### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...

    HDU题目java实现

    8. **图论与树**:HDU题目中可能涉及图的遍历(深度优先搜索DFS、广度优先搜索BFS)、树的遍历(前序、中序、后序)以及最小生成树、最短路径等算法。 9. **动态规划**:这是一种优化策略,通过构建状态转移方程来...

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    个人训练实用知识库分享知识分享

    通过在树状数组中进行更新和查询,我们可以解决树形问题。 六、并查集 在2020“远光杯”网络资格赛M排除危险中,我们学习了并查集的应用。并查集是一种数据结构,用于解决图论相关的问题。通过在并查集中进行 ...

    HDU DP动态规划

    【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...

    hdu 300+ AC 代码

    线段树在处理动态区间问题时非常有效,如在数组上进行区间加法、区间求和等操作。理解和熟练运用线段树是解决复杂数据结构题目的关键。 3. **字符串处理**:字符串是编程中常见的数据类型,用于处理文本信息。字符...

    HH神总结的线段树专辑-超经典的

    它可以用来解决一系列与区间有关的问题,例如区间求和、区间最值等问题。相较于其他数据结构如平衡二叉搜索树等,线段树在实现上更加简洁且易于理解。 本文作者提到,在早期撰写的一篇关于线段树的文章中,虽然得到...

    hdu 的2072,2084,2082,1170,ac代码

    HDU 2084题要求我们对数组进行操作,这通常与矩阵处理相关。代码实现的过程中,首先读取矩阵的大小和矩阵本身的数据,然后进行特定的矩阵压缩操作。这类问题不仅考验了我们对二维数组的控制能力,还要求我们理解并...

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...

    hdu动态规划算法集锦

    根据提供的信息,我们可以总结出以下关于“hdu动态规划算法集锦”的知识点: ### 动态规划基础概念 动态规划是一种解决多阶段决策问题的方法,它通过将原问题分解为互相重叠的子问题,利用子问题的解来构建原问题...

    hdu 3333 turing tree 解题报告

    题目“HDU 3333 Turing Tree”要求解决的问题是:给定一个整数序列和一系列区间,计算每个区间内不重复数字的和。由于数据规模较大(N ,000, K ,000),直接的暴力方法效率过低,因此我们需要采用一种更高效的数据...

    杭电ACMhdu1163

    2. **数据结构**:常用的数据结构包括数组、链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)、图等,对于不同的问题,选择合适的数据结构能有效提高解题效率。 3. **字符串处理**:杭电ACM中的题目可能涉及到...

    Hdu1000—2169部分代码

    HDU是杭州电子科技大学(Hangzhou Dianzi University)举办的一个在线编程竞赛平台,全称为HDU Online Judge。ACM是国际大学生程序设计竞赛(International Collegiate Programming Contest)的缩写,是一个全球性的...

Global site tag (gtag.js) - Google Analytics