사용자 도구

사이트 도구


ps:problems:boj:16975

수열과 쿼리 21

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

구간 쿼리

시간복잡도O(n+mlogn)
인풋사이즈n<=100,000, m<=100,000
사용한 언어Python 3.11
제출기록43396KB / 432ms
최고기록632ms
해결날짜2023/01/17
태그

38단계

풀이

  • 구간 업데이트와 포인트 쿼리를 요구하는 문제이다.
  • lazy propagation을 지원하는 세그먼트 트리를 이용해서 푸는 방법도 있지만, 원소의 값을 구간합으로 처리하는 테크닉을 사용하면, 포인트 업데이트와 구간합 쿼리 문제로 변환할 수 있다. 이렇게 푸는 쪽이 단순한 펜윅 트리만을 이용해서 풀 수 있으므로 더 간단하고 빠르게 해결 가능하다.
  • lazy propagation을 지원하는 세그먼트 트리를 사용하든, 펜윅트리를 사용하든, 트리를 만드는 데에 O(n), m개의 쿼리를 각각 처리하는 데에 O(logn)이 걸린다. 따라서 총 시간복잡도는 O(n+mlogn)

코드

"""Solution code for "BOJ 16975. 수열과 쿼리 21".

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

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

    fenwick = fenwicktree.FenwickTreeForRangeUpdatePointQuery(A)
    for _ in range(M):
        match sys.stdin.readline().split():
            case ['1', i, j, k]:
                fenwick.range_update(int(i) - 1, int(j), int(k))
            case ['2', x]:
                print(fenwick.get(int(x) - 1))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
P R E I B
 
ps/problems/boj/16975.txt · 마지막으로 수정됨: 2023/01/17 08:10 저자 teferi