HDU 1754 I Hate It (段树单点更新)

HDU 1754 I Hate It (段树单点更新)

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

Problem Description
很多学校更受欢迎的习惯。

老师们真的很喜欢问。从XX XX到其中,的是多少。
这让非常多学生非常反感。

无论你喜不喜欢,如今须要你做的是,就是依照老师的要求。写一个程序,模拟老师的询问。当然。老师有时候须要更新某位同学的成绩。

 

Input
本题目包括多组測试。请处理到文件结束。

在每一个測试的第一行。有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 ),分别代表学生的数目和操作的数目。

学生ID编号分别从1编到N。
第二行包括N个整数,代表这N个学生的初始成绩。当中第i个数代表ID为i的学生的成绩。
接下来有M行。

每一行有一个字符 C (仅仅取’Q’或’U’) 。和两个正整数A,B。
当C为’Q’的时候。表示这是一条询问操作。它询问ID从A到B(包含A,B)的学生其中,成绩最高的是多少。
当C为’U’的时候。表示这是一条更新操作,要求把ID为A的学生的成绩更改为B。

 

Output
对于每一次询问操作,在一行里面输出最高成绩。
 

Sample Input
   
   
5 6 1 2 3 4 5 Q 1 5 U 3 6 Q 3 4 Q 4 5 U 2 9 Q 1 5

 

Sample Output
   
   
5 6 5 9
Hint
Huge input,the C function scanf() will work better than cin

 

感觉没什么好说的,这是我线段树的入门题,感觉效果非常好

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(x,y) ((x+y)>>1)
using namespace std;
#define N 200005

struct stud{
int le,ri;
int va;
}f[N*4];

int a[N];

void pushup(int pos)
{
    f[pos].va=max(f[L(pos)].va,f[R(pos)].va);
}

void build(int pos,int le,int ri)
{
    f[pos].le=le;
    f[pos].ri=ri;

    if(le==ri)
    {
      f[pos].va=a[le];
      return ;
    }
    int mid=MID(le,ri);

    build(L(pos),le,mid);
    build(R(pos),mid+1,ri);

   pushup(pos);
}

void update(int pos,int le,int ri)
{
    if(f[pos].le==le&&f[pos].ri==le)
    {
        f[pos].va=ri;
        return ;
    }

    int mid=MID(f[pos].le,f[pos].ri);

    if(mid>=le)
        update(L(pos),le,ri);
    else
        update(R(pos),le,ri);

    pushup(pos);
}

int query(int pos,int le,int ri)
{
   if(f[pos].le>=le&&f[pos].ri<=ri)
   {
       return f[pos].va;
   }

   int mid=MID(f[pos].le,f[pos].ri);

   if(mid>=ri)
    return query(L(pos),le,ri);
   else
    if(mid<le)
    return query(R(pos),le,ri);
   else
      return max(query(L(pos),le,mid),query(R(pos),mid+1,ri));
}

int main()
{
    int n,m,i;

    while(~scanf("%d%d",&n,&m))
    {
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);

         build(1,1,n);

        char c[10];
        int le,ri;

        while(m--)
        {
            scanf("%s%d%d",c,&le,&ri);

            if(c[0]=='Q')
                printf("%d\n",query(1,le,ri));
            else
                update(1,le,ri);
        }
    }
    return 0;
}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117345.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Ubuntu 15.10 安装 Rabbitvcs

    Ubuntu 15.10 安装 Rabbitvcsppa按回车继续或者Ctrl+c取消添加gpg:钥匙环‘/tmp/tmp_70d0zm5/secring.gpg’已建立gpg:钥匙环‘/tmp/tmp_70d0zm5/pubring.gpg’已建立gpg:下载密钥‘34EF4A35’,从hkp服务器keyserver.ubuntu.comgpg:/tmp/tmp_70d0zm5/trustdb.gpg:建立了信任度数据库gpg:密钥34EF4A35:公钥“LaunchpadRabbitVCS”已导入gpg:合计被处理的数量:1g

  • c语言socket 释放,C语言socket编程

    c语言socket 释放,C语言socket编程8种机械键盘轴体对比本人程序员,要买一个写代码的键盘,请问红轴和茶轴怎么选?[codelanguage=”cpp”]structsockaddr{unsignedshortsa_family;charsa_data[14];};[/code]这是一个16字节大小的结构(2+14),sa_family可以认为是socketaddressfamily的缩写,也可能被简写成AF…

  • 关于JS全局变量问题

    关于JS全局变量问题最近在easyui使用全局变量的时候老是执行if判断语句,而不执行顺序下来的局部赋值。导致老是提示undefined;经网上查询得知JS全局变量时:当全局变量跟局部变量重名时,局部变量的scope会覆盖掉全局变量的scope,当离开局部变量的scope后,又重回到全局变量的scope。Javascript的变量的scope是根据方法块来划分的(也就是说以function的一对大括号{}来划分

  • Vue集成activity工作流

    Vue集成activity工作流情景:由于activiti与系统应用主题样式出入较大,协商后决定将activiti的editor-app放在前台。ps:内网开发,无图,凭记忆摘取主要内容。步骤:将activiti放在public即静态目录下。 通过iframe在相应的前台工作流界面引入activiti的model.html(最外层的主html,名字可能有出入)。 mounted时将this,即vuecompo…

  • ETL的基础知识,看完你就全明白了!「建议收藏」

    ETL的基础知识,看完你就全明白了!「建议收藏」深度解析了ETL的基础概念以及实现方案,很值得一看~

  • 两个栈实现一个队列

    用栈实现队列1、栈的特点栈的特点是先进后出,进出元素都是在同一端(栈顶)。入栈:出栈:2、队列的特点队列的特点是先进先出,出入元素是在不同的两端(队头和队尾)。入队:出队:3、两个栈实现队列我们拥有两个栈,可以让其中一个栈作为队列的入口,负责插入新元素;另一个栈作为队列的出口,负责移除老的元素。队列的主要操作无非有两个:入队和出队。在…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号