[백준/파이썬][Gold IV] Organizing Beads - 23178

[Gold IV] Organizing Beads - 23178

문제 링크

성능 요약

메모리: 123408 KB, 시간: 380 ms

분류

자료 구조, 그리디 알고리즘, 트리를 사용한 집합과 맵

제출 일자

2025년 2월 18일 22:42:15

문제 설명

Hyunuk has a long barrel of n$n$ (2≤n≤2⋅105$2 \le n \le 2 \cdot 10^5$) cells. Each cell is either empty or contains a bead. When storing beads, it doesn't look good if they are scattered here and there, so Hyunuk wants to gather all the beads at one end. Specifically, if the barrel has k$k$ beads, the beads must be in cells 1$1$ through k$k$ or in cells n−k+1$n-k+1$ through k$k$.

Hyunuk can move the bead in the i$i$-th cell of the barrel to the (i−1$i-1$)-th cell or the (i+1$i+1$)-th cell by lightly pushing it. If there is a bead in the cell to be moved, that bead is also pushed in the same direction. For example, let there be beads in the 2nd, 3rd, and 5th cells. If Hyunuk pushes the bead in the 2nd cell to the 3rd cell, the bead in the 3rd cell is also pushed to the 4th cell. The bead in the 5th cell remains in place.

Hyunuk wonders how the minimum number of moves required to organize all beads will change when he adds or removes beads from the barrel. Write a program that calculates the minimum number of moves required to organize the bead barrel as Hyunuk inserts or removes beads from the barrel.

입력

The first line contains a single integer n (2≤n≤2⋅105)$n\ (2 \le n \le 2 \cdot 10^5)$, the length of the bead barrel.

The second line contains a string of length n$n$ consisting of only O's and X's representing the state of the bead barrel. If the i$i$-th character of the string is O, then the cell has a bead in it. Otherwise, the i$i$-th character of the string is X and the cell is empty.

The third line contains a single integer q (1≤q≤2⋅105)$q\ (1 \le q \le 2 \cdot 10^5)$, the number of actions performed by Hyunuk.

The next q$q$ lines each contain a single integer k (1≤k≤n)$k\ (1 \le k \le n)$ representing Hyunuk's action. This means that if there is a bead in the k$k$-th cell of the barrel, the bead is removed, and if there is no bead, it is inserted at the corresponding position.

The input will be designed such that the barrel will never have zero beads.

출력

Output q$q$ lines, the i$i$-th of which contains a single integer, the minimum number of moves required to organize all beads after Hyunuk's first i$i$ actions.

풀이

class Fenw :
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, i, delta):
        while i <= self.n :
            self.tree[i] += delta
            i += i & -i

    def query(self, i):
        s = 0
        while i :
            s += self.tree[i]
            i -= i & -i
        return s

    def find(self, v):
        idx = 0
        bit_mask = 1 << (self.n.bit_length() - 1)
        while bit_mask :
            t = idx + bit_mask
            if t <= self.n and self.tree[t] < v :
                v -= self.tree[t]
                idx = t
            bit_mask //= 2
        return idx + 1

def sol_23178() :
    n = int(input())
    beads = list(input().rstrip())

    q = int(input())

    BIT = Fenw(n)
    state = [False] * (n + 1)

    for i, ch in enumerate(beads, 1) :
        if ch == 'O' :
            state[i] = True
            BIT.update(i, 1)

    for _ in range(q) :
        k = int(input())
        if state[k] :
            state[k] = False
            BIT.update(k, -1)
        else :
            state[k] = True
            BIT.update(k, 1)

        total = BIT.query(n)
        l = BIT.find(1)
        r = BIT.find(total)

        ans = min(r - total, n - l + 1 - total)
        print(ans)

sol_23178()

이 문제는 아직 내 수준에서는 풀 수 없는 문제인 듯 하다. 열심히 공부하자