만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

구슬

면접 대비

시간 제한1초메모리 제한256 MB

요약
상자에 구슬을 더하는 연산과 구간 합 질의를 순서대로 처리해 각 질의 결과를 출력합니다.
난이도

쉬움10점 중 3점

유형
세그먼트 트리
정답자
아직 제출이 없습니다

문제

구슬을 상자에 넣는 놀이가 있다. 규칙은 여기에 다 적기 어려울 만큼 복잡하지만, 승부를 가르는 데 필요한 정보는 하나뿐이다. 서로 붙어 있는 상자 구간에 구슬이 몇 개 들어 있는지를 계속 파악하는 것이다.

친구가 이 놀이를 매번 이기도록 도와주는 프로그램을 만들어 달라고 부탁했다. 한 판이 시작될 때 모든 상자는 비어 있다.

입력

첫 줄에 진행하는 판의 수 TT가 주어진다. 각 판은 상자의 수 BB, 넣기 요청의 수 PP, 질의 요청의 수 QQ를 차례로 담은 줄로 시작한다.

이어서 P+QP + Q개의 줄이 주어진다. 각 줄은 P i a 또는 Q i j 형식이다. P i a는 ii번 상자에 구슬 aa개를 넣는다는 뜻이고, Q i j는 그 시점에 ii번 상자부터 jj번 상자까지 들어 있는 구슬의 개수를 묻는다는 뜻이다. 양쪽 끝 상자도 범위에 포함된다.

  • 0<T≤1000 < T \le 100
  • 0<B≤1000000 < B \le 100000
  • 0<P≤300000 < P \le 30000
  • 0<Q≤300000 < Q \le 30000
  • 0≤a≤1000 \le a \le 100
  • P i a에서 0<i≤B0 < i \le B이다.
  • Q i j에서 0<i≤j≤B0 < i \le j \le B이다.
  • 상자 번호는 1번부터 시작한다.
  • 입출력의 양이 많다. 입력은 버퍼를 쓰는 방식으로 읽고, 출력은 전부 모은 뒤 한 번에 내보내는 편이 좋다.

출력

질의 요청마다 그 시점에 ii번 상자부터 jj번 상자까지 들어 있는 구슬의 총 개수를 한 줄에 하나씩 출력한다.

예제5

  1. 예제 1

    입력
    1
7 5 3
P 2 1
P 3 3
P 4 7
Q 1 4
P 7 6
Q 4 4
P 6 4
Q 1 7
    예상 출력
    11
7
21

  2. 예제 2

    입력
    1
1 1 1
P 1 100
Q 1 1
    예상 출력
    100

  3. 예제 3

    입력
    1
5 3 4
Q 1 5
P 3 0
Q 3 3
P 1 0
Q 1 1
P 5 9
Q 1 5
    예상 출력
    0
0
0
9

  4. 예제 4

    입력
    3
2 1 1
P 1 5
Q 1 2
4 2 2
P 4 8
Q 4 4
P 1 2
Q 1 4
1 1 1
P 1 0
Q 1 1
    예상 출력
    5
8
10
0

  5. 예제 5

    입력
    1
3 6 3
P 2 100
P 2 100
Q 2 2
P 2 100
P 2 100
P 2 100
Q 1 3
P 2 100
Q 2 3
    예상 출력
    200
500
600