13537 수열과 쿼리 1 python

https://www.acmicpc.net/problem/13537

13537번: 수열과 쿼리 1

 

 

 

 

문제 접근

세그먼트 트리에 재미붙어서 풀다가 발견한 문제다.

순서대로 쭉 풀어볼까 싶기도 한 문제인데... 다이아급 문제는 거를거같다. 너무빡새ㅜ

세그먼트 트리로 구현하는데, 부분정렬시키면서 트리를 구현했다.

풀고 알았는데 머지 소트 트리라고 이미 있는 방법이다.

부분정렬 시킨 트리에서 범위에 포함되는 노드들을 선택해서 k보다 큰값을 탐색해서 return하면 된다.

그리고 k보다 큰 값을 찾는부분은 upperbound로 구현해야 시간초과가 없다.

 

 

 

예시의 첫번째 2~4까지를 탐색하는 경우

파란 동그라미 2군대만 확인하면 된다.

 

 

 

 

 

코드

import sys
import math

input = sys.stdin.readline
"""
1. 
"""

N = int(input())
A = list(map(int, input().split()))
M = int(input())

left, right, val = 0, 0, 0
node = 2**math.ceil(math.log2(N))
tree = [[] for i in range(node * 2 + 1)]

for i in range(N):
  tree[node + i] = [A[i]]


def init(index):
  if index < node:
    tree[index] = sorted(init(index * 2) + init(index * 2 + 1))
  return tree[index]


def update(start, end, index):
  if start > right or end < left:
    return 0
  if left <= start and end <= right:
    return upperBound(tree[index])

  mid = (start + end) // 2
  return update(start, mid, index * 2) + update(mid + 1, end, index * 2 + 1)


def upperBound(arr):
  l = 0
  r = len(arr)
  while l < r:
    m = (l + r) // 2
    if arr[m] > val: r = m
    else: l = m + 1
  return len(arr) - l


init(1)

for m in range(M):
  left, right, val = map(int, input().split())
  left, right = left, right
  print(update(1, node, 1))