1270. 数列区间最大值
摘要
Title: 1270. 数列区间最大值
Tag: 线段树
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
1270. 数列区间最大值
-
题意
输入一串数字，给你 M 个询问，每次询问就给你两个数字 X,Y，要求你说出 X 到 Y 这段区间内的最大数。
-
思路
线段树求区间最大值
-
代码
线段树常数太大了，而且读入数据也多，导致超时
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'''
Author: NEFU AB-IN
Date: 2022-03-26 17:50:51
FilePath: \ACM\Acwing\1264.1.py
LastEditTime: 2022-03-26 21:03:12
'''
class Node():
def __init__(self, l, r):
self.l = l
self.r = r
self.max = -1
N = int(1e5 + 10)
tr = [Node(0, 0) for _ in range(N << 2)]
a = [0] * N
def pushup(p):
tr[p].max = max(tr[p << 1].max, tr[p << 1 | 1].max)
def build(p, l, r):
tr[p] = Node(l, r)
if l == r:
tr[p].max = a[l]
return
mid = l + r >> 1
build(p << 1, l, mid)
build(p << 1 | 1, mid + 1, r)
pushup(p)
def modify(p, k, v):
if k <= tr[p].l and tr[p].r <= k:
tr[p].max = v
return
mid = tr[p].l + tr[p].r >> 1
if k <= mid: modify(p << 1, k, v)
if k > mid: modify(p << 1 | 1, k, v)
pushup(p)
def query(p, l, r):
ans = -1
if l <= tr[p].l and tr[p].r <= r:
return tr[p].max
mid = tr[p].l + tr[p].r >> 1
if l <= mid: ans = max(ans, query(p << 1, l, r))
if r > mid: ans = max(ans, query(p << 1 | 1, l, r))
return ans
n, m = map(int, input().split())
a[1:] = list(map(int, input().split()))
build(1, 1, n)
for i in range(m):
x, y = map(int, input().split())
print(query(1, x, y))