테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 수열과 쿼리 1 ======

===== 풀이 =====
  * [[ps:구간 쿼리#구간_내에서_x보다_작은_수의_갯수_rank|구간 rank 쿼리]]의 기본 문제.
  * [[ps:구간 쿼리#구간_내에서_x보다_작은_수의_갯수_rank|구간 rank 쿼리]]에서 설명했듯이, 오프라인 쿼리로 풀 수 있는 경우에는, [[ps:Order Statistic Tree]]를 써서 푸는 것이 가장 효율적이다. 구체적인 방법은 링크 참조.
    * Persistent Segment Tree나 머지소트트리를 사용하는 솔루션은 [[ps:problems:boj:13544|수열과 쿼리 3]]를 참고. 저 문제는 이 문제와 다른 조건이 거의 동일하지만 오프라인 쿼리가 불가능하도록 변형한 문제이다.
  * 값의 범위가 10^9 이므로 [[ps: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))%% 이다


===== 코드 =====
<dkpr py>
"""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()

</dkpr>
  * Dependency: [[:ps:teflib:fenwicktree#OrderStatisticTree|teflib.fenwicktree.OrderStatisticTree]]

{{tag>BOJ ps:problems:boj:플래티넘_4}}