Powered by:NEFU AB-IN

Link

1270. 数列区间最大值

• 题意

  输入一串数字，给你 M 个询问，每次询问就给你两个数字 X,Y，要求你说出 X 到 Y 这段区间内的最大数。

• 思路

  线段树求区间最大值

• 代码

  超时

  '''
  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))