注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Minary_Acdream

http://f10.moe/

 
 
 

日志

 
 

I Hate It  

2012-07-12 22:56:37|  分类: 线段树 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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

Hint

Huge input,the C function scanf() will work better than cin 
 
这是上一题的变形,所以代码类似,这题直接A了>。 <


#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;

#define MAXN 200000
#define LC(a) ((a << 1) + 1) ///< 左儿子下标
#define RC(a) ((a << 1) + 2) ///< 右儿子下标
#define MID(a, b) ((a + b) >> 1) ///< 求中点
struct node
{
int l,r;
int mid;
int _max;

}T[MAXN * 4];
int num[MAXN];

void create(int p, int l, int r)
{
T[p].l = l, T[p].r = r, T[p].mid = MID(l, r);
if(l == r)
{
T[p]._max = num[l - 1];
return;
}
create(LC(p), l, T[p].mid);
create(RC(p), T[p].mid + 1, r);
T[p]._max = max(T[LC(p)]._max ,T[RC(p)]._max);
}

void update(int p, int i, int num) ///< num有正负
{
if(T[p].l == T[p].r)
{
T[p]._max = num;
//break;
return ;
}
if(i <= T[p].mid) update(LC(p), i, num);
else update(RC(p), i, num);

/** 更新该节点的sum */
T[p]._max =max(T[LC(p)]._max ,T[RC(p)]._max);
}

int query(int p, int l, int r)
{
if(T[p].l == l && T[p].r == r) return T[p]._max;

if(r <= T[p].mid) return query(LC(p), l, r);
else
if(l > T[p].mid) return query(RC(p), l, r);
else return max(query(LC(p), l, T[p].mid) ,query(RC(p), T[p].mid + 1, r));
}

int main()
{
int N,M;
while(cin>>N>>M)
{
for(int i =0 ;i < N;i ++) scanf("%d",&num[i]);
create(0,1,N);
while(M --)
{
char a;
int A,B;
//a = getchar();
//scanf("%d%d",&A,&B);
cin>>a>>A>>B;
if(a == 'Q') cout<<query(0,A,B)<<endl;
if(a == 'U') update(0,A,B);

}
}
}
/*
M,N,C,A,B
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
*/



  评论这张
 
阅读(125)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018