hdu1754

发表于 | 分类于 ， ， | 阅读数 次

链接:hdu1754

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

    题解

  • 单点查询区间修改
  • 线段树模板题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int N=1e6;
ll tr[N<<2];
int n,m,a[N];

void build(int o,int l,int r){
    if(l==r)tr[o]=a[l];
	else {
		int mid=l+r>>1;
		build(o<<1,l,mid);
		build(o<<1|1,mid+1,r);
		tr[o]=max(tr[o<<1],tr[o<<1|1]);
	}
}


void update(int o,int l,int r,int pos,int k){
	if(l==r)tr[o]=k;
	else {
		int mid=l+r>>1;
		if(pos<=mid)update(o<<1,l,mid,pos,k);
		else update(o<<1|1,mid+1,r,pos,k);
		tr[o]=max(tr[o<<1],tr[o<<1|1]);
	}
}

ll ask(int o,int l,int r,int L,int R){
	if(L>r||R<l)return -1;
	if(L<=l&&R>=r)return tr[o];
	int mid=l+r>>1;
	int p1=ask(o<<1,l,mid,L,R),p2=ask(o<<1|1,mid+1,r,L,R);
	return max(p1,p2);
}

int main(){
	ios::sync_with_stdio(false);
	while(cin>>n>>m){
		rep(i,1,n)cin>>a[i];
		build(1,1,n);
		while(m--){
			int x,y;
			char c;
			cin>>c>>x>>y;
			if(c=='Q')cout<<ask(1,1,n,x,y)<<endl;
			else update(1,1,n,x,y);
		}
	}
	return 0;
}