HDUJ 1754 I Hate It[通俗易懂]

HDUJ 1754 I Hate It

大家好,又见面了,我是全栈君。

I Hate It

Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 37856    Accepted Submission(s): 14981

Problem Description
非常多学校流行一种比較的习惯。老师们非常喜欢询问,从某某到某某其中,分数最高的是多少。

这让非常多学生非常反感。

无论你喜不喜欢,如今须要你做的是,就是依照老师的要求。写一个程序,模拟老师的询问。

当然,老师有时候须要更新某位同学的成绩。

 

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

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

int a[200005];
int p[200005];
int n,m;

int lowbit(int x)
{
    return x&(-x);
}

void build()
{
    int i,j;
    for(i=1;i<=n;i++)
    {
        p[i]=a[i];
        for(j=1;j<lowbit(i);j<<=1)
        {
            if(p[i]<p[i-j])
                p[i]=p[i-j];
        }
    }
}

void insert(int i,int x)
{
    a[i]=x;
    while(i<=n)
    {
        if(p[i]<x)
            p[i]=x;
        else     break;

        i += lowbit(i);
    }
}

int query(int l,int r)
{
    int maxn=a[r];
    while(true)
    {
        if(maxn<a[r])
            maxn=a[r];
        if(l==r)   break;

        for(r-=1;r-l>=lowbit(r);r-=lowbit(r))
        {
            if(maxn<p[r])
                maxn=p[r];
        }
    }
    return maxn;
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(p,0,sizeof p);
        int i;
        for(i=1;i<=n;i++)
            scanf("%d",a+i);
        build();

        char c[3];
        int x,y;
        for(i=1;i<=m;i++)
        {
            scanf("%s%d%d",c,&x,&y);

            if(c[0]=='Q')
                printf("%d\n",query(x,y));
            else
                insert(x,y);
        }
    }

    return 0;
}

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

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

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

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

(0)


相关推荐

  • next()nextLine()以及nextInt()的区别及用法

    next()nextLine()以及nextInt()的区别及用法next()、nextLine()、nextInt()作为scanner内置的方法,常常让人傻傻分不清楚,今天在这里记下他们的区别以及以此区别为出发点的用法:他们的区别在于对于空格的处理方式不同,以及返回值不同。使用nextLine()方法时,不将空格看做是两个字符串的间隔,而是看作字符串的一部分,返回时,它作为String类型一并返回:publicclassdemo{ pub

  • docker(11)Dockerfile 中的COPY与ADD 命令

    docker(11)Dockerfile 中的COPY与ADD 命令前言Dockerfile中提供了两个非常相似的命令COPY和ADD,本文尝试解释这两个命令的基本功能,以及其异同点,然后总结其各自适合的应用场景。Build上下文的概念在使用dock

  • electron preload 提前_electron vue3

    electron preload 提前_electron vue3背景最近手头的electron项目需要做一个报告导出的功能,导出时要弹出个页面,可让用户自行补全相应的字段。由于公司已有现成的笔录工具,现直接将其集成进来,用webview直接展示其笔录页面,将已有的值传给笔录。webview简介electron的webview标签时基于Chromiumwebview,由于Chromium的架构变化巨大,会影响electronwebview的稳定性,包括呈现、导航和事件路由。所以electron团队不建议使用webview标

    2022年10月26日
  • 进销存ERP源码 小程序源码 APP源码

    进销存ERP源码 小程序源码 APP源码进销存ERP源码+小程序源码+APP源码+H5系统简介:常规管理系统配置 附件管理 个人资料 数据库管理分类管理用于统一管理网站的所有分类,分类可进行无限级分类,分类类型请在常规管理->系统配置->字典配置中添加权限管理管理员管理 管理员日志 角色组会员管理会员管理 会员分组 会员规则进销存管理1、商品管理商品分类商品信息商品单位2、库存管理商品存库库存流水盘点单

  • Linux curl命令最全详解

    Linux curl命令最全详解目录一、最常用的curl命令1、发送GET请求2、发送POST请求3、发送json格式请求:二、curl命令语法与curl命令参数详解1、curl命令语法2、curl命令参数详解三、Linuxcurl命令退出码四、常见用法1、下载(option:-o或者option:-O)2、上传文件(option:-T)3、伪造来源页面|伪造referer|盗链(option:-e)4、伪造代理设备(模仿浏览器)5、设置http请求6、http响应头7.

  • tensorflow2.0卷积神经网络_python神经网络框架

    tensorflow2.0卷积神经网络_python神经网络框架卷积神经网络一般用来处理图像信息,对于序列这种一维的数据而言,我们就得采用一维的卷积,tensorflow中提供有专用的函数conv1d,各参数的使用说明如下:conv1d参数说明value输入数据,value的格式为:[batch,in_width,in_channels],batch为样本维,表示多少个样本,in_width为宽度维,表示样本的宽度,in_channels维通道维,表示样本有多少个通道。filters卷积核,filters的格式为:[filter_wi

发表回复

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

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