I Hate It 【线段树】

题目链接HDU-1754

[kuangbin带你飞]专题七 线段树

题目描述

很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。
这让很多学生很反感。

不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。


思路

单点修改,区间询问最值,典型的RMQ问题;这里用线段树写的;
树状数组和RMQ问题,大多数都可以利用线段树来解决!

代码

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>
using namespace std;

#define MAX 200010

struct Node{
int l, r, Max;
}tree[MAX * 4];

void push_up(int k)
{
tree[k].Max = max(tree[k<<1].Max, tree[k<<1|1].Max);
}

void build(int k, int l, int r)
{
tree[k].l = l, tree[k].r = r;
if(l == r)
{
cin >> tree[k].Max;
}
else
{
int mid = (l + r) >> 1;
build(k<<1, l, mid);
build(k<<1|1, mid+1, r);
push_up(k);
}
}

void updata(int k, int l, int r, int val)
{
int L = tree[k].l, R = tree[k].r;
if(l <= L && R <= r)
{
tree[k].Max = val;
}
else
{
int mid = (L + R) >> 1;
if(l <= mid)
updata(k<<1, l, r, val);
if(mid < r)
updata(k<<1|1, l, r, val);
push_up(k);
}
}

int query(int k, int l, int r)
{
int L = tree[k].l, R = tree[k].r;
if(l <= L && R <= r)
{
return tree[k].Max;
}
else
{
int tmp = -0x3f3f3f3f;
int mid = (L + R) >> 1;
if(l <= mid)
tmp = max(tmp, query(k<<1, l, r));
if(mid < r)
tmp = max(tmp, query(k<<1|1, l, r));
return tmp;
}
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
while(cin >> n >> m)
{
build(1, 1, n);
for(int i = 1; i<=m; i++)
{
string s;
cin >> s;
if(s == "Q")
{
int x, y;
cin >> x >> y;
cout << query(1, x, y) << endl;
}
else
{
int x, val;
cin >> x >> val;
updata(1, x, x, val);
}
}
}
return 0;
}
-------------本文结束,感谢您的阅读!-------------