수열과 쿼리 1

• 구간 rank 쿼리의 기본 문제.
• 구간 rank 쿼리에서 설명했듯이, 오프라인 쿼리로 풀 수 있는 경우에는, Order Statistic Tree를 써서 푸는 것이 가장 효율적이다. 구체적인 방법은 링크 참조.
  • Persistent Segment Tree나 머지소트트리를 사용하는 솔루션은 수열과 쿼리 3를 참고. 저 문제는 이 문제와 다른 조건이 거의 동일하지만 오프라인 쿼리가 불가능하도록 변형한 문제이다.
• 값의 범위가 10^9 이므로 Order Statistic Tree를 사용하기 위해서는 값을 압축하는 작업이 필요하다.
• m개의 쿼리를 정렬하는 데에 O(mlogm), n+m개의 수를 압축하는 데에 O((n+m)log(n+m)). 압축된 범위로 이루어진 Order Statistic Tree는 숫자 삽입과 rank쿼리를 각각 O(log(n+m))에 처리하므로, n번의 삽입과 m번의 rank를 처리하는 데에는 O((n+m)log(n+m)). 총 시간복잡도는 O((n+m)log(n+m)) 이다

"""Solution code for "BOJ 13537. 수열과 쿼리 1".

- Problem link: https://www.acmicpc.net/problem/13537
- Solution link: http://www.teferi.net/ps/problems/boj/13537
"""

import sys
from teflib import fenwicktree


def main():
    N = int(sys.stdin.readline())  # pylint: disable=unused-variable
    A = [int(x) for x in sys.stdin.readline().split()]
    M = int(sys.stdin.readline())
    beg_queries = [[] for _ in range(N)]
    end_queries = [[] for _ in range(N)]
    answers = [0] * M
    nums_to_compress = set(A)
    for query_num in range(M):
        i, j, k = [int(x) for x in sys.stdin.readline().split()]
        nums_to_compress.add(k)
        beg_queries[i - 1].append((k, query_num))
        end_queries[j - 1].append((k, query_num))

    compress_map = {x: i for i, x in enumerate(sorted(nums_to_compress))}
    nums = fenwicktree.OrderStatisticTree(len(compress_map))
    for i, a_i in enumerate(A):
        for k, query_num in beg_queries[i]:
            comp_k = compress_map[k]
            answers[query_num] -= nums.size() - nums.count_less_than(comp_k + 1)
        nums.add(compress_map[a_i])
        for k, query_num in end_queries[i]:
            comp_k = compress_map[k]
            answers[query_num] += nums.size() - nums.count_less_than(comp_k + 1)
        
    print(*answers, sep='\n')    


if __name__ == '__main__':
    main()

• Dependency: teflib.fenwicktree.OrderStatisticTree