hdu1574 I Hate It (线段树,查询区间最大值)

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

模板题,改改就行了!注意!!!没事别读%c,容易出事,所以都转化成字符串读入代码如下:
 1 #include <bits/stdc++.h>
 2
 3 using namespace std;
 4 #define M 200200
 5 #define inf 0x3f3f3f3f
 6 struct segTree
 7 {
 8     int l,r,elem;
 9     int mid()
10     {
11         return (l+r)/2;
12     }
13 }tree[4*M];
14 int n,m,ans;
15 void buildTree (int now,int left,int right)
16 {
17     tree[now].l=left;
18     tree[now].r=right;
19     if (left==right)
20     {
21         scanf("%d",&tree[now].elem);
22         return;
23     }
24     int middle=tree[now].mid();
25     buildTree(now<<1,left,middle);
26     buildTree(now<<1|1,middle+1,right);
27     tree[now].elem=max(tree[now<<1].elem,tree[now<<1|1].elem);
28 }
29 void update (int now,int left,int right,int x,int change)
30 {
31     if (left==right)
32     {
33         tree[now].elem=change;
34         return;
35     }
36     int middle=tree[now].mid();
37     if (x<=middle)
38     update(now<<1,left,middle,x,change);
39     else
40     update(now<<1|1,middle+1,right,x,change);
41     tree[now].elem=max(tree[now<<1].elem,tree[now<<1|1].elem);
42 }
43 void query (int now,int left,int right,int L,int R)
44 {
45     if (L<=left&&right<=R)
46     {
47         ans=max(ans,tree[now].elem);
48         return ;
49     }
50     int middle=tree[now].mid();
51     if (R<=middle)
52     query(now<<1,left,middle,L,R);
53     else if (L>middle)
54     query(now<<1|1,middle+1,right,L,R);
55     else
56     {
57          query(now<<1,left,middle,L,R);
58          query(now<<1|1,middle+1,right,L,R);
59     }
60 }
61 int main()
62 {
63     //freopen("de.txt","r",stdin);
64     while (~scanf("%d%d",&n,&m))
65     {
66         buildTree(1,1,n);
67         char op[6];
68         while (m--)
69         {
70             int x,y;
71             scanf("%s",op);
72             scanf("%d%d",&x,&y);
73             if (op[0]==‘U‘)
74             update(1,1,n,x,y);
75             else
76             {
77                 ans=-inf;
78                 query(1,1,n,x,y);
79                 printf("%d\n",ans);
80             }
81         }
82     }
83     return 0;
84 }
				



				
时间: 09-15

hdu1574 I Hate It (线段树,查询区间最大值)的相关文章

HDU 2795 Billboard 【线段树维护区间最大值&amp;&amp;查询变形】

任意门:http://acm.hdu.edu.cn/showproblem.php?pid=2795 Billboard Time Limit: 20000/8000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 28743    Accepted Submission(s): 11651 Problem Description At the entrance to the un

HDU5692 dfs + 线段树维护区间最大值

先附上题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5692 Problem Description 百度科技园内有n个零食机,零食机之间通过n−1条路相互连通.每个零食机都有一个值v,表示为小度熊提供零食的价值. 由于零食被频繁的消耗和补充,零食机的价值v会时常发生变化.小度熊只能从编号为0的零食机出发,并且每个零食机至多经过一次.另外,小度熊会对某个零食机的零食有所偏爱,要求路线上必须有那个零食机. 为小度熊规划一个路线,使得路线上的价值总和最

nyoj1185 最大最小值 (线段树求区间最大值和最小值)

对于不懂线段树的,先看为这篇文章理解下.点击打开链接 这道题普通方法 ,TLE. 最大最小值 时间限制:1000 ms  |  内存限制:65535 KB 难度:2 描述 给出N个整数,执行M次询问. 对于每次询问,首先输入三个整数C.L.R: 如果C等于1,输出第L个数到第R个数之间的最小值: 如果C等于2,输出第L个数到第R个数之间的最大值: 如果C等于3,输出第L个数到第R个数之间的最小值与最大值的和. (包括第L个数和第R个数). 输入 首先输入一个整数T(T≤100),表示有T组数据.

【线段树查询区间最值】poj 3264 Balanced Lineup

1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 5 const int maxn=50005; 6 struct Seg 7 { 8 int l,r,mi,ma; 9 }tree[maxn*4]; 10 int val[maxn]; 11 12 void build(int l,int r,int i=1) 13 { 14 tree[i].l=l; 15 tree[i].r=r; 16 if (l=

hdoj 5443 The Water Problem【线段树求区间最大值】

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5443 刷道水题助助兴 #include<stdio.h> #include<string.h> #include<algorithm> #include<stack> #define MAX 2100 #define INF 0x7fffff using namespace std; int n,m; int Max[MAX]; void pushup(int

最敏捷的机器人(线段树维护区间最值)

题面: Wind设计了很多机器人.但是它们都认为自己是最强的,于是,一场比赛开始了--机器人们都想知道谁是最敏捷的,于是它们进行了如下一个比赛.首先,他们面前会有一排共n个数,它们比赛看谁能最先把每连续k个数中最大和最小值写下来,当然,这些机器人运算速度都很,它们比赛的是谁写得快.但是Wind也想知道答案,你能帮助他吗? Input: 每组测试数据 第1行为n,k(1<=k<=n<=100000) 第2行共n个数,为数字序列,所有数字均在int范围内. Output: 共n-k+1行 第

POJ 2528 Mayor&#39;s posters(线段树,区间覆盖,单点查询)

Mayor's posters Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 45703   Accepted: 13239 Description The citizens of Bytetown, AB, could not stand that the candidates in the mayoral election campaign have been placing their electoral post

BZOJ 3110 ZJOI 2013 K大数查询 树套树(权值线段树套区间线段树)

题目大意:有一些位置,这些位置上可以放若干个数字.现在有两种操作. 1.在区间l到r上添加一个数字x 2.求出l到r上的第k大的数字是什么 思路:这种题一看就是树套树,关键是怎么套,怎么写.(话说我也不会来着..)最容易想到的方法就是区间线段树套一个权值线段树,但是区间线段树上的标记就会变得异常复杂.所以我们就反过来套,用权值线段树套区间线段树.这样修改操作在外线段树上就变成了单点修改,外线段树就不用维护标记了.在里面的区间线段树上维护标记就容易多了.具体实现见代码. CODE: #includ

hihoCode 1078 : 线段树的区间修改

#1078 : 线段树的区间修改 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 对于小Ho表现出的对线段树的理解,小Hi表示挺满意的,但是满意就够了么?于是小Hi将问题改了改,又出给了小Ho: 假设货架上从左到右摆放了N种商品,并且依次标号为1到N,其中标号为i的商品的价格为Pi.小Hi的每次操作分为两种可能,第一种是修改价格——小Hi给出一段区间[L, R]和一个新的价格NewP,所有标号在这段区间中的商品的价格都变成NewP.第二种操作是询问——小Hi给出一段

HDU 1540 &amp;&amp; POJ 2892 Tunnel Warfare (线段树,区间合并).

~~~~ 第一次遇到线段树合并的题,又被律爷教做人.TAT. ~~~~ 线段树的题意都很好理解吧.. 题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1540 http://poj.org/problem?id=2892 ~~~~ 我的代码:200ms #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #defin