首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >HDU-1754 I Hate It(线段树)

HDU-1754 I Hate It(线段树)

作者头像
ShenduCC
发布2018-04-25 17:28:55
6000
发布2018-04-25 17:28:55
举报
文章被收录于专栏:算法修养算法修养

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

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;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2015-12-29 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 阿里云-云翼计划礼上加礼#——买六个月送域名代金券!
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档