사용자 도구

사이트 도구


ps:problems:boj:13544

수열과 쿼리 3

ps
링크acmicpc.net/…
출처BOJ
문제 번호13544
문제명수열과 쿼리 3
레벨플래티넘 3
분류

구간 쿼리

시간복잡도O(nlogn + mlog^2(n))
인풋사이즈n<=100,000, m<=100,000
사용한 언어Python
제출기록69240KB / 1620ms
최고기록1620ms
해결날짜2021/05/02

풀이

  • 구간 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()

토론

댓글을 입력하세요:
D P U B X
 
ps/problems/boj/13544.txt · 마지막으로 수정됨: 2021/05/03 14:55 저자 teferi