HDU-1754 I Hate It(线段树)

阿里云-云翼计划礼上加礼#——买六个月送域名代金券!

I Hate It

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

Problem Description 很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。 这让很多学生很反感。

不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。

Input 本题目包含多组测试,请处理到文件结束。 在每个测试的第一行,有两个正整数 N 和 M ( 0

#include <iostream>
#include <math.h>
#include <stdlib.h>

#include <string.h>

using namespace std;

int c[4000001];
int n,m;
char a;
int x,y;
int max(int x,int y)
{
    return x>y?x:y;
}
void PushUp(int node)
{
    c[node]=max(c[node<<1],c[node<<1|1]);
}
void build(int node,int begin,int end)
{
    if(begin==end)
    {
       scanf("%d",&c[node]);
        return;
    }
    int m=(begin+end)>>1;
    build(node<<1,begin,m);
    build(node<<1|1,m+1,end);
    PushUp(node);
}
void Update(int node,int begin,int end,int ind,int num)
{
    if(begin==end)
    {
        c[node]=num;
        return;
    }
    int m=(begin+end)>>1;
    if(ind<=m)
        Update(node<<1,begin,m,ind,num);
    else
        Update(node<<1|1,m+1,end,ind,num);
    PushUp(node);
}
int Query(int node,int begin,int end,int left,int right)
{
    if(left<=begin&&end<=right)
        return c[node];
    int m=(begin+end)>>1;
    int ret=0;
    if(left<=m)
        ret=max(ret,Query(node<<1,begin,m,left,right));
    if(right>m)
        ret=max(ret,Query(node<<1|1,m+1,end,left,right));
    return ret;

}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
       build(1,1,n);

        for(int i=0;i<m;i++)
        {
            getchar();
          scanf("%c",&a);
          scanf("%d%d",&x,&y);
          if(a=='Q')
          {
            printf("%d\n",Query(1,1,n,x,y));
          }
          else
          {
            Update(1,1,n,x,y);
          }
        }

    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

UESTC 30 &&HDU 2544最短路【Floyd求解裸题】

最短路 Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/...

30730
来自专栏ml

hdu 1598 find the most comfortable road(枚举+卡鲁斯卡尔最小生成树)

find the most comfortable road Time Limit: 1000/1000 MS (Java/Others)    Memory ...

30140
来自专栏ml

HDUOJ---1754 I Hate It (线段树之单点更新查区间最大值)

I Hate It Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K ...

32540
来自专栏牛客网

看了这么多大佬的面经,想来应该回馈一波

21800
来自专栏ml

hdu----(1257)最少拦截系统(dp/LIS)

最少拦截系统 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Ja...

31350
来自专栏数据和云

Thinking in SQL系列之:供需分配问题

编辑手记:SQL做为一种编程语言,能够满足各类数据处理的需要,关键就在于算法与思维方式。以SQL会友,希望结交更多的数据库、数据分析领域的朋友。 推荐阅读: T...

36290
来自专栏Android先生

Dagger2神器入门

网上随便搜索一下Dragger2,一大堆文章铺天盖地而来,一上来就讲@Inject,@Module等注解是做什么的,解释一大堆,看完之后一脸懵逼。对于刚刚入门D...

11120
来自专栏钱曙光的专栏

一周极客热文:程序员必须知道的10大基础实用算法及其讲解

程序员必须知道的10大基础实用算法及其讲解,包括: 快速排序算法; 堆排序算法(Heapsort):是指利用堆这种数据结构所设计的一种排序算法; 归并排序(Me...

22070
来自专栏小樱的经验随笔

HDU 2037 今年暑假不AC(贪心,区间更新,板子题)

今年暑假不AC Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (J...

36450
来自专栏ml

HDUOJ----2063过山车

过山车 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/...

33660

扫码关注云+社区

领取腾讯云代金券