수열과 쿼리 3

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

"""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()