博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hdoj p1754——I Hate It(线段树)
阅读量:4565 次
发布时间:2019-06-08

本文共 2169 字,大约阅读时间需要 7 分钟。

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

 

线段树。。。框架基本相同,多的只有判断max了,在建树中加上就OK。

 

 

#include<cstring>

#define L(u) (u*2)
#define R(u) (u*2+1)
#define MAXN 200005
using namespace std;
int n,m;
int a[MAXN];
struct node{
  int l,r;
  int maxx;
}s[MAXN*4];
int ans=0;
int max(int a,int b)
{
  if(a>b)return a;
  return b;
}
void buildtree(int u,int left,int right)
{
  s[u].l=left,s[u].r=right;
  if(left==right)
  {
    s[u].maxx=a[left];
    return ;
  }
  int mid=(s[u].l+s[u].r)>>1;
  buildtree(L(u),left,mid);
  buildtree(R(u),mid+1,right);
  s[u].maxx=max(s[L(u)].maxx,s[R(u)].maxx);
}
void pushup(int u)
{
  s[u].maxx=max(s[L(u)].maxx,s[R(u)].maxx);
}
void update(int u,int x,int qwe)
{
  if(s[u].l==x&&s[u].r==x)
  {
    s[u].maxx=qwe;
    return ;
  }
  int mid=(s[u].l+s[u].r)>>1;
  if(x>mid)update(R(u),x,qwe);
  else update(L(u),x,qwe);
  pushup(u);
}
void findmax(int u,int left,int right)
{
  if(s[u].l==left&&s[u].r==right)
  {
    ans=max(ans,s[u].maxx);
    return ;
  }
  int mid=(s[u].l+s[u].r)>>1;
  if(left>mid)findmax(R(u),left,right);
  else if(right<=mid)findmax(L(u),left,right);
  else
  {
    findmax(L(u),left,mid);
    findmax(R(u),mid+1,right);
  }
}
int main()
{
  ios::sync_with_stdio(false);
  while(cin>>n>>m)
  {
    memset(a,0,sizeof(a));
    memset(s,0,sizeof(s));
    for(int i=1;i<=n;i++)
    cin>>a[i];
    buildtree(1,1,n);
    for(int i=1;i<=m;i++)
    {
      char b;cin>>b;
      if(b=='Q')
      {
        ans=0;
        int x,y;cin>>x>>y;
        findmax(1,x,y);
        cout<<ans<<endl;
      }
      else

      {

        int x,y;cin>>x>>y;
        update(1,x,y);
      }
    }
  }
}

 

转载于:https://www.cnblogs.com/937337156Zhang/p/5668018.html

你可能感兴趣的文章
vue 如何在循环中绑定v-model
查看>>
shell脚本
查看>>
[代码笔记]JS保持函数单一职责,灵活组合
查看>>
cmd 重定向
查看>>
【IOS开发】如何画1像素的线
查看>>
【计算机视觉】双目测距(五)--匹配算法对比
查看>>
KMP模板
查看>>
luogu 1314 聪明的质检员
查看>>
[转载]求职者防骗必读!楼主亲身经历告诉你岗前培训多么不靠谱而且违法!
查看>>
Hibernate内存溢出分析一例
查看>>
基于Axis1.4的webservice接口开发(接口调用)
查看>>
Hive内置函数详解
查看>>
【转】MyEclipse快捷键大全
查看>>
IT职业技能图谱10--Hadoop家族技能图谱
查看>>
Java - 反射(1)
查看>>
控制台中显示执行的Sql语句
查看>>
Linux(Centos7)下搭建SVN服务器
查看>>
安卓开发的Tasks and Back Stack
查看>>
Ansi,UTF8,Unicode编码
查看>>
原子变量的性能问题
查看>>