만드는 중입니다

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

자료구조 퀴즈

시간 제한8초메모리 제한512 MB

요약
n×n 격자에 m1개의 직사각형 구간 덧셈을 적용한 뒤, 각 질의 직사각형 안의 최댓값을 구합니다.
난이도

어려움10점 중 9점

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

문제

KD-tree를 배운 뒤 다음 문제를 떠올렸다. 이 자료구조를 점검하기에 좋은 문제일 것이다.

처음에 n×nn \times n 행렬 AA의 모든 원소는 0이다.

먼저 구간 덧셈 연산을 m1m_1번 수행한다. 각 연산에서는 x1,y1,x2,y2,wx_1, y_1, x_2, y_2, w가 주어지며 (1≤x1≤x2≤n1 \le x_1 \le x_2 \le n, 1≤y1≤y2≤n1 \le y_1 \le y_2 \le n), x1≤i≤x2x_1 \le i \le x_2이고 y1≤j≤y2y_1 \le j \le y_2인 모든 Ai,jA_{i,j}에 ww를 더한다.

그다음 구간 최댓값 질의를 m2m_2번 수행한다. 각 질의에서는 x1,y1,x2,y2x_1, y_1, x_2, y_2가 주어지며 (1≤x1≤x2≤n1 \le x_1 \le x_2 \le n, 1≤y1≤y2≤n1 \le y_1 \le y_2 \le n), x1≤i≤x2x_1 \le i \le x_2이고 y1≤j≤y2y_1 \le j \le y_2를 만족하는 Ai,jA_{i,j} 중 최댓값을 구한다.

입력

첫째 줄에 세 정수 nn, m1m_1, m2m_2가 주어진다 (1≤n≤5⋅1041 \le n \le 5 \cdot 10^4, 1≤m1≤5⋅1041 \le m_1 \le 5 \cdot 10^4, 1≤m2≤5⋅1051 \le m_2 \le 5 \cdot 10^5).

이후 m1m_1개 줄에 다섯 정수 x1,y1,x2,y2,wx_1, y_1, x_2, y_2, w가 한 줄에 하나씩 주어진다 (1≤x1≤x2≤n1 \le x_1 \le x_2 \le n, 1≤y1≤y2≤n1 \le y_1 \le y_2 \le n, 1≤w≤1091 \le w \le 10^9).

이후 m2m_2개 줄에 네 정수 x1,y1,x2,y2x_1, y_1, x_2, y_2가 주어진다 (1≤x1≤x2≤n1 \le x_1 \le x_2 \le n, 1≤y1≤y2≤n1 \le y_1 \le y_2 \le n).

출력

m2m_2개 줄에 각 질의의 답을 한 정수로 출력한다.

예제1

  1. 예제 1

    입력
    5 5 5
1 1 4 5 4
4 1 4 1 10
1 3 3 3 3
1 1 5 5 8
2 4 4 5 8
2 1 2 1
4 1 5 4
1 2 3 5
2 1 5 3
1 3 5 5
    예상 출력
    12
22
20
22
20