[BOJ] 1321 - 군인

[백준] 1321 - 군인

접근

매 쿼리가 들어왔을 때 1번 부대부터 n번 부대까지의 구간합을 각각 알아낼 수 있다면 lower_bound로 O(logN)만에 답을 탐색할 수 있다.

구현

값의 업데이트가 많이 일어나므로 세그먼트 트리 또는 펜윅트리를 사용한다.(나는 구현이 좀 더 쉬운 펜윅트리를 사용했다.)
펜윅트리나 세그먼트 트리로 저장할 경우 lower_bound를 사용할 수가 없으므로 직접 이분탐색을 통해 탐색하여 구현했다.
즉, 부대 번호를 mid값으로 하여 탐색하고 해당 부대까지의 인원 합이 작으면 들어갈 수 없으므로 L을 올리고, 내 군번보다 큰 값을 가진다면 들어갈 수 있으므로 R을 내리면서 탐색했다.

소스코드

n = int(input())
tree = [0 for _ in range(n+5)]

def update(idx, v):
    while idx<=n:
        tree[idx]+=v
        idx += idx & (-idx)

def find(idx):
    rtn = 0
    while idx>0:
        rtn += tree[idx]
        idx -= idx & (-idx)
    return rtn

i = 1
for a in input().split():
    update(i, int(a))
    i+=1

for i in range(int(input())):
    a = input().split()
    if a[0] == '1':
        update(int(a[1]), int(a[2]))
    else :
        L = 1
        R = n
        while True:
            mid = (L+R)//2
            ck = find(mid) >= int(a[1])
            if L == mid:
                if not ck:
                    L = R
                break
            if ck:
                R = mid
            else:
                L=mid
        print(L)