카테시안 트리 (Cartesian Tree)

# Cartesian Tree: 스택 빌드 O(N), RMQ via LCA
import sys
input = sys.stdin.readline
​
class Node:
  def __init__(self, idx, val):
      self.idx = idx
      self.val = val
      self.left = None
      self.right = None
​
def build_cartesian(a):
  stack = []
  for i, v in enumerate(a):
      last = None
      while stack and a[stack[-1].idx] >= v:
          last = stack.pop()
      node = Node(i, v)
      if stack:
          stack[-1].right = node
      if last:
          node.left = last
      stack.append(node)
  return stack[0] if stack else None
​
def LCA(root, l, r):
  if not root or root.idx < l or root.idx > r:
      return None
  if l <= root.idx <= r:
      return root
  left_lca = LCA(root.left, l, r)
  right_lca = LCA(root.right, l, r)
  if left_lca and right_lca:
      return root
  return left_lca if left_lca else right_lca
​
def RMQ(root, l, r):
  lca = LCA(root, l, r)
  return lca.val if lca else float('inf')
​
n, q = map(int, input().split())
a = list(map(int, input().split()))
root = build_cartesian(a)
out = []
for _ in range(q):
  l, r = map(int, input().split())
  out.append(str(RMQ(root, l - 1, r - 1)))
print("\n".join(out))

// Cartesian Tree: Stack 빌드 O(N), RMQ via LCA
import java.util.*;
import java.io.*;
public class Main {
  static class Node {
      int idx, val;
      Node left = null, right = null;
      Node(int i, int v) { idx = i; val = v; }
  }
​
  static Node buildCartesian(int[] a) {
      Stack<Node> st = new Stack<>();
      for (int i = 0; i < a.length; i++) {
          Node last = null;
          while (!st.isEmpty() && a[st.peek().idx] >= a[i]) {
              last = st.pop();
          }
          Node node = new Node(i, a[i]);
          if (!st.isEmpty()) st.peek().right = node;
          if (last != null) node.left = last;
          st.push(node);
      }
      while (st.size() > 1) st.pop();
      return st.isEmpty() ? null : st.peek();
  }
​
  static Node LCA(Node root, int l, int r) {
      if (root == null || root.idx < l || root.idx > r) return null;
      if (l <= root.idx && root.idx <= r) return root;
      Node left_lca = LCA(root.left, l, r);
      Node right_lca = LCA(root.right, l, r);
      if (left_lca != null && right_lca != null) return root;
      return left_lca != null ? left_lca : right_lca;
  }
​
  static int RMQ(Node root, int l, int r) {
      Node lca = LCA(root, l, r);
      return lca != null ? lca.val : Integer.MAX_VALUE;
  }
​
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int q = Integer.parseInt(st.nextToken());
      int[] a = new int[n];
      st = new StringTokenizer(br.readLine());
      for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken());
      Node root = buildCartesian(a);
      StringBuilder sb = new StringBuilder();
      while (q-- > 0) {
          st = new StringTokenizer(br.readLine());
          int l = Integer.parseInt(st.nextToken()) - 1;
          int r = Integer.parseInt(st.nextToken()) - 1;
          sb.append(RMQ(root, l, r)).append('\n');
      }
      System.out.print(sb);
  }
}