군인

• 문제 설명이 좀 이해하기 어렵게 되어있는데, 이해하고 나면 간단한 k번째수 쿼리 문제가 된다.
• 군인들의 부대 번호를 집합에 저장한다고 생각하자. 1번 부대에 4명, 2번 부대에 3명, 3번 부대에 2명이면 {1,1,1,1,2,2,2,3,3} 이런식.
• 이제 i번 군인이 몇번 부대냐고 묻는 것은, 저 집합에서 i번째로 큰 수가 뭐냐고 묻는 것과 동일하다.
• 부대의 감원과 증원은, 저 집합에서 i인 값을 a개 더하거나 빼는 것과 동일하다
• 따라서 펜윅트리나 세그먼트 트리 기반의 Order Statistic Tree를 사용하면 쉽게 이 두가지 쿼리를 처리할 수 있다. 두가지 연산 모두 O(logn)에 처리된다
• 전체 시간복잡도는 Order Statistic Tree를 구축하는데에 O(n), m개의 명령을 처리하는 데에 O(mlogn). 합쳐서 O(n+mlogn)이다

"""Solution code for "BOJ 1321. 군인".

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

import sys
from teflib import fenwicktree


def main():
    N = int(sys.stdin.readline())  # pylint: disable=unused-variable
    soldiers = fenwicktree.OrderStatisticTree(
        int(x) for x in sys.stdin.readline().split())
    M = int(sys.stdin.readline())
    for _ in range(M):
        query = [int(x) for x in sys.stdin.readline().split()]
        if query[0] == 1:
            soldiers.add(query[1] - 1, query[2])
        else:
            print(soldiers.kth(query[1]) + 1)


if __name__ == '__main__':
    main()

• Dependency: teflib.segmenttree.OrderStatisticTree