백준 17400 - 깃발춤 (Python)

문제 정보

• https://www.acmicpc.net/problem/17400
• 세그먼트 트리, 홀짝성

---

문제 정리

깃발춤 공연은 카리스마가 $c_i$의 값을 가진 N명의 사람들이 일렬로 서서 진행하는 공연이다.
깃발춤 공연 중 교대 깃발춤 동작이 있는데, 구간 [L, R]의 사람들이 깃발을 흔든다. L번째 공연자와의 거리가 짝수인 공연자들은 깃발을 왼쪽으로 흔들고, 홀수인 공연자들은 깃발을 오른쪽으로 흔든다.
깃발춤 균일도는 왼쪽으로 흔든 공연자들의 카리스마 합과 오른쪽으로 흔든 공연자들의 카리스마 합의 차이의 절댓값으로 정의된다.
교대 깃발춤 동작이 Q번 주어질 때, 매 교대 깃발춤의 균일도를 구해야 한다.

---

풀이

• 홀짝으로 분리된 구간합 쿼리를 Q번 처리하는 문제이다. $N \leq 300,000$, $Q \leq 300,000$이므로 세그먼트 트리로 $O(QlogN)$의 시간에 처리해야 함을 알 수 있다.

• 홀수번째 사람들의 카리스마를 저장하는 세그먼트 트리와 짝수번째 사람들의 카리스마를 저장하는 세그먼트 트리 총 2개를 두어 각 쿼리별로 홀수 구간, 짝수 구간을 분리하고 쿼리를 처리해주는 방식으로 해결할 수 있다.

• 그러나 길이가 1칸인 경우 또는 3칸인 경우 나머지 처리와 구간 처리가 귀찮아지게 된다.

• 여기서 한 가지 관찰을 할 수 있다.
  어차피 홀수 사람의 합 - 짝수 사람의 합을 구하고 절댓값을 씌울거면, 처음부터 홀수번째 사람의 값을 반전시켜 저장하자!
  이렇게 하면 그냥 [L, R] 구간합 쿼리가 된다.

---

후기

처음에 홀짝 세그먼트 트리 2개로 관리하다가 분리해야 하는 케이스가 너무 많아져 포기하고 부호 반전시키는 풀이로 바꾸게 되었다.

---

코드

# 백준 17400

import io

input = io.BufferedReader(io.FileIO(0), 1<<18).readline


def build(N, A):
    tree = [0] * (2*N)
    for i in range(len(A)):
        if i % 2 == 0:
            tree[i+N] = A[i]
        else:
            tree[i+N] = -A[i]
    for i in range(N-1, 0, -1):
        tree[i] = tree[i<<1] + tree[i<<1 | 1]

    return tree


# 점 업데이트
def update(N, tree, index, value):
    index += N
    tree[index] += value

    while index > 1:
        index >>= 1
        tree[index] = tree[index<<1] + tree[index<<1 | 1]


# 구간 쿼리
def query(N, tree, left, right):
    result = 0
    left += N
    right += N

    while left <= right:
        if left & 1:
            result += tree[left]
            left += 1
        if ~right & 1:
            result += tree[right]
            right -= 1
        left >>= 1
        right >>= 1
    
    return result


def main():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    size = 1<<N.bit_length()
    tree = build(size, A)

    for _ in range(Q):
        a, b, c = map(int, input().split())
        b -= 1
        if a == 1:
            c -= 1
            print(abs(query(size, tree, b, c)))
        elif b % 2 == 0:
            update(size, tree, b, c)
        else:
            update(size, tree, b, -c)


main()