boj1321.cpp

#include <iostream>
#include <stdio.h>
using namespace std;
 
int N, K;
int p = 1;
int A[500000*4];
 
//구간 트리를 갱신하는 함수
void part_update(int temp1){
        //temp1의 부모 부터 시작
        int parent = ((p + temp1 - 1) >> 1);
        for (int i = parent; i >= 1; i >>= 1)
        A[i] = A[i * 2] + A[i * 2 + 1];     
}
 
//해당 병사가 몇번 부대에 해당하는지 찾아주는 함수
int find(int number){
    int index = 1;
    //index가 최하층 도달 전까지 반복 한다.
    while (index < p){
        //왼쪽 갈지 오른쪽 갈지 결정하자.
        if (A[index * 2] < number){ //병사 번호가 왼쪽 값보다 클 때
            number -= A[index * 2];
            //인덱스를 오른쪽으로 보내버려
            index = index * 2 + 1;
        }
        else{ //병사 번호가 왼쪽 값보다 같거나 작을 때
            index *= 2;
        }
    }
    return index-p+1;
}
 
int main(){
    //부대 수 입력 받기
    scanf("%d", &N);
    int temp, temp1, temp2;
    //인덱스 p찾기
    while (N > p) p <<= 1;
    //최하층 초기화
    for (int i = 0; i < N; i++){
        scanf("%d", &temp);
        A[p + i] = temp;
    }
    //부모 초기화
    for (int i = p - 1; i >= 1; i--)
        A[i] = A[i * 2] + A[i * 2 + 1];
     
    //명령 수 입력
    scanf("%d", &K);
    //명령 처리
    for (int i = 0; i < K; i++){
        scanf("%d", &temp);
        if (temp == 1){ //1번 명령
            scanf("%d%d", &temp1, &temp2);
            //구간 트리 갱신
            A[p + temp1 - 1] += temp2;
            part_update(temp1);
        }
        else{ //2번 명령
            scanf("%d", &temp);
            printf("%d\n", find(temp));         
        }
    }
    return 0;
}