시간에 따른 직사각형 합
다이아몬드 IV의견: 0
2차원 평면에서 점을 추가하거나 직사각형 영역의 가중치 합을 묻는 작업을 처리한다. 처음에는 점이 하나도 없다.
\(Q\)개의 작업이 순서대로 주어진다. 각 작업은 다음 중 하나이다.
-
1 x y w: 좌표 \((x, y)\)에 가중치 \(w\)의 점을 추가한다. (같은 좌표에 여러 점이 있을 수 있다) -
2 x1 y1 x2 y2: 지금까지 추가된 점들 중 \(x_1 \le x \le x_2\), \(y_1 \le y \le y_2\)를 만족하는 점들의 가중치 합을 출력한다.
좌표 범위가 매우 크므로 좌표 압축이 필요하고, 작업의 시간 순서를 지켜야 한다.
\(1 \le Q \le 50{,}000\)
\(0 \le x, y \le 10^9\)
\(|w| \le 10^6\)
\(0 \le x_1 \le x_2 \le 10^9\), \(0 \le y_1 \le y_2 \le 10^9\)
첫 줄에 작업의 수 \(Q\)가 주어진다.
이어서 \(Q\)개의 줄에 위 형식의 작업이 한 줄에 하나씩 주어진다.
각 2번 작업에 대해 가중치 합을 한 줄에 하나씩 출력한다.
6
1 1 1 5
1 3 4 2
2 0 0 2 2
1 3 4 3
2 2 3 4 5
2 0 0 10 10
5
5
10(1,1,w5),(3,4,w2) 추가. [0,0]-[2,2] 안에는 (1,1)만 -> 5. (3,4,w3) 추가 후 [2,3]-[4,5] 안에는 (3,4)가 둘(w2,w3) -> 5. 전체 합 5+2+3 = 10.
4
2 0 0 10 10
1 5 5 7
2 0 0 4 4
2 5 5 5 5
0
0
7점이 없을 때 질의 -> 0. (5,5,w7) 추가 후 [0,0]-[4,4]에는 없음 -> 0. 점 (5,5)만 포함하는 질의 -> 7.
riseoj 작성
출처 Original
평가 및 의견
시간에 따른 직사각형 합
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
시간에 따른 직사각형 합