테페리넷

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

===== 풀이 =====
  * [[ps:구간 쿼리#구간 Rank 쿼리]] 에서 오프라인 쿼리 풀이를 막아놓은 버전.
    * 오프라인 쿼리가 막힌것만 제외하면 [[ps:problems:boj:13537|수열과 쿼리 1]]과 동일하다. 오프라인 쿼리 풀이 방식을 보고 싶으면 그쪽을 참고.
  * [[ps:구간 쿼리#구간 Rank 쿼리]]에서 설명했듯 PST를 사용하는 풀이 (시간복잡도 %%O((n+q)logm)%%) 보다 머지소트트리를 사용하는 풀이 (시간복잡도 O(nlogn + qlog^2(n))) 가 더 빠르게 동작한다. 각 방법에 대한 설명은 링크 참고.
  * 아래 코드에는 머지소트트리를 사용하는 풀이만 첨부했다

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 13544. 수열과 쿼리 3".

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

import bisect
import sys


class MergeSortTree:
    def __init__(self, values):
        self._tree = [[x] for x in values]
        self._size = len(self._tree)
        self._tree = [None] * self._size + self._tree
        for i in range(self._size - 1, 0, -1):
            self._tree[i] = sorted(self._tree[i * 2] + self._tree[i * 2 + 1])

    def count_less_than(self, beg: int, end: int, k: int):
        l, r = beg + self._size, end + self._size - 1
        ret = 0
        while l <= r:
            if l % 2:
                ret += bisect.bisect_left(self._tree[l], k)
            if not r % 2:
                ret += bisect.bisect_left(self._tree[r], k)
            l, r = (l + 1) >> 1, (r - 1) >> 1
        return ret


def main():
    N = int(sys.stdin.readline())
    A = [int(x) for x in sys.stdin.readline().split()]
    M = int(sys.stdin.readline())
    num_set = MergeSortTree(A)
    last_ans = 0
    for _ in range(M):
        i, j, k = [int(x) for x in sys.stdin.readline().split()]
        i, j, k = i ^ last_ans, j ^ last_ans, k ^ last_ans
        last_ans = (j - i + 1) - num_set.count_less_than(i - 1, j, k + 1)
        print(last_ans)


if __name__ == '__main__':
    main()

</dkpr>
{{tag>BOJ ps:problems:boj:플래티넘_3}}