머지 소트 트리 (Merge Sort Tree)

# Merge Sort Tree: bisect 로 upper_bound
import sys
from bisect import bisect_right
input = sys.stdin.readline
​
class MergeSortTree:
  def __init__(self, a):
      self.n = len(a)
      self.tree = [[] for _ in range(4 * self.n)]
      self.build(1, 0, self.n - 1, a)
​
  def build(self, node, l, r, a):
      if l == r:
          self.tree[node] = [a[l]]
          return
      mid = (l + r) // 2
      self.build(2 * node, l, mid, a)
      self.build(2 * node + 1, mid + 1, r, a)
      # merge
      self.tree[node] = sorted(self.tree[2 * node] + self.tree[2 * node + 1])
​
  def count_le(self, node, tl, tr, ql, qr, k):
      if ql > tr or qr < tl:
          return 0
      if ql <= tl and tr <= qr:
          return bisect_right(self.tree[node], k)
      mid = (tl + tr) // 2
      return (self.count_le(2 * node, tl, mid, ql, qr, k) +
              self.count_le(2 * node + 1, mid + 1, tr, ql, qr, k))
​
  def query(self, l, r, k):
      return self.count_le(1, 0, self.n - 1, l, r, k)
​
n, q = map(int, input().split())
a = list(map(int, input().split()))
mst = MergeSortTree(a)
out = []
for _ in range(q):
  l, r, k = map(int, input().split())
  out.append(str(mst.query(l - 1, r - 1, k)))
print("\n".join(out))

// Merge Sort Tree: Collections.binarySearch 로 upper_bound
import java.util.*;
import java.io.*;
public class Main {
  static class MergeSortTree {
      int n;
      List<Integer>[] tree;
​
      @SuppressWarnings("unchecked")
      MergeSortTree(int[] a) {
          n = a.length;
          tree = new ArrayList[4 * n];
          for (int i = 0; i < tree.length; i++) tree[i] = new ArrayList<>();
          build(1, 0, n - 1, a);
      }
​
      void build(int node, int l, int r, int[] a) {
          if (l == r) {
              tree[node].add(a[l]);
              return;
          }
          int mid = (l + r) / 2;
          build(2 * node, l, mid, a);
          build(2 * node + 1, mid + 1, r, a);
          // merge
          List<Integer> left = tree[2 * node];
          List<Integer> right = tree[2 * node + 1];
          int i = 0, j = 0;
          while (i < left.size() || j < right.size()) {
              if (i >= left.size()) tree[node].add(right.get(j++));
              else if (j >= right.size()) tree[node].add(left.get(i++));
              else tree[node].add(left.get(i) <= right.get(j) ? left.get(i++) : right.get(j++));
          }
      }
​
      int countLe(int node, int tl, int tr, int ql, int qr, int k) {
          if (ql > tr || qr < tl) return 0;
          if (ql <= tl && tr <= qr) {
              int pos = Collections.binarySearch(tree[node], k);
              if (pos < 0) pos = -pos - 1;
              else {
                  while (pos < tree[node].size() && tree[node].get(pos) == k) pos++;
              }
              return pos;
          }
          int mid = (tl + tr) / 2;
          return countLe(2 * node, tl, mid, ql, qr, k)
               + countLe(2 * node + 1, mid + 1, tr, ql, qr, k);
      }
​
      int query(int l, int r, int k) {
          return countLe(1, 0, n - 1, l, r, k);
      }
  }
​
  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());
      MergeSortTree mst = new MergeSortTree(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;
          int k = Integer.parseInt(st.nextToken());
          sb.append(mst.query(l, r, k)).append('\n');
      }
      System.out.print(sb);
  }
}