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)


相关推荐

  • 帮你彻底搞懂JS中的prototype、__proto__与constructor(图解)

    帮你彻底搞懂JS中的prototype、__proto__与constructor(图解)  作为一名前端工程师,必须搞懂JS中的prototype、__proto__与constructor属性,相信很多初学者对这些属性存在许多困惑,容易把它们混淆,本文旨在帮助大家理清它们之间的关系并彻底搞懂它们。这里说明一点,__proto__属性的两边是各由两个下划线构成(这里为了方便大家看清,在两下划线之间加入了一个空格:__proto__)。  现在正式开始!让我们从如下一个简单的例…

  • 开心网外挂程序_快乐西游怎么开内挂

    开心网外挂程序_快乐西游怎么开内挂参阅:http://code.google.com/p/kaixin/转载于:https://www.cnblogs.com/scgw/archive/2009/05/07/1451899.html

  • 微信 网页授权_微信解除其他app授权

    微信 网页授权_微信解除其他app授权一、背景近期实现微信招聘公众号的需求,需要在微信用户同意公众号授权后,获取到微信用户信息。这一步操作在前端无法完成,所以这里我们使用了C#WebApi项目,通过接口实现后台获取微信用户数据再重定向到前端页面。二、思路具体而言,微信网页授权流程分为四步:1、引导用户进入授权页面同意授权,获取code;2、通过code换取网页授权access_toke…

    2022年10月25日
  • 排序算法汇总总结

    排序算法汇总总结

  • allure生成的报告怎么查看_allure测试报告

    allure生成的报告怎么查看_allure测试报告原因可能由于:因为pytest-allure-adaptor库基本被python3放弃了,运行很不友好,所以报错解决方法:terminal中先卸载:pipuninstallpytest-allure-adaptor再安装:pipallure-pytest若安装找不到该模块可以去设置那下载…

  • mac 安装golang2021 激活码_在线激活

    (mac 安装golang2021 激活码)2021最新分享一个能用的的激活码出来,希望能帮到需要激活的朋友。目前这个是能用的,但是用的人多了之后也会失效,会不定时更新的,大家持续关注此网站~IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html…

发表回复

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

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