아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

모키아

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

요약
셀에 고객 수를 더하는 갱신 이후 입력된 순서대로 직사각형 영역 안 고객 수 합을 구합니다.
난이도

어려움10점 중 8점

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

문제

몰도바의 이동통신 회사 모키아가 새 고객 위치 추적 시스템을 만들었다. 다른 위치 추적 시스템처럼 "고객 C는 어디에 있는가?"라는 질의에 밀리미터 단위로 답하고, 여기에 더해 "주어진 직사각형 구역 안에 고객이 몇 명 있는가?"라는 질의에도 답한다.

이 시스템은 세상을 한 변의 길이가 WW인 정사각형으로 보고, 그 정사각형을 1×11 \times 1 크기의 칸으로 나눈다. 칸 하나는 두 인덱스 (x,y)(x, y)로 정하며 1≤x,y≤W1 \le x, y \le W이다. 인덱스는 1부터 시작한다. 예를 들어 크기가 4×44 \times 4인 표에서는 1≤x≤41 \le x \le 4이고 1≤y≤41 \le y \le 4이다.

주어진 직사각형 구역 안에 고객이 몇 명 있는지 구하는 프로그램을 작성하시오.

입력

명령은 한 줄에 하나씩 주어진다. 각 줄은 명령을 나타내는 정수 하나와 그 명령의 매개변수로 이루어진다.

명령매개변수뜻
0W모든 칸이 0인 W×WW \times W 크기의 표를 만든다. 이 명령은 맨 처음에 한 번만 주어진다.
1x y A칸 (x,y)(x, y)의 고객 수에 AA를 더한다. AA는 양의 정수이다.
2X1 Y1 X2 Y2X1≤x≤X2X_1 \le x \le X_2이고 Y1≤y≤Y2Y_1 \le y \le Y_2인 칸 (x,y)(x, y)에 있는 고객 수의 합을 묻는다.
3없음프로그램을 끝낸다. 이 명령은 맨 마지막에 한 번만 주어진다.

질의는 그 앞에 나온 더하기 명령만 반영한다. 명령이 2가 아닌 줄에는 아무것도 출력하지 않는다.

출력

명령 2마다 물어본 고객 수를 한 줄에 하나씩, 질의가 주어진 순서대로 출력한다.

제한

  • 1≤W≤2 000 0001 \le W \le 2\,000\,000
  • 1≤X1≤X2≤W1 \le X_1 \le X_2 \le W
  • 1≤Y1≤Y2≤W1 \le Y_1 \le Y_2 \le W
  • 1≤x,y≤W1 \le x, y \le W
  • 0<A≤10 0000 < A \le 10\,000
  • 명령 1은 160,000개를 넘지 않는다.
  • 명령 2는 10,000개를 넘지 않는다.

예제2

  1. 예제 1

    입력
    0 4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3
    예상 출력
    3
5

  2. 예제 2

    입력
    0 1
2 1 1 1 1
1 1 1 5
2 1 1 1 1
1 1 1 7
2 1 1 1 1
3
    예상 출력
    0
5
12