만드는 중입니다

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

MST와 직사각형

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

요약
N×N 행렬 A에 Q개의 직사각형 영역 쿼리로 값을 더한 뒤, A[i][j]를 간선 비용으로 하는 완전 그래프의 최소 스패닝 트리 비용을 구합니다.
난이도

어려움10점 중 8점

유형
최소 신장 트리, 누적 합, 유니온 파인드
정답자
아직 제출이 없습니다

문제

크기가 N×NN \times N인 2차원 배열 AA가 있다. 처음에 모든 칸의 값은 0이다.

QQ개의 질의가 주어진다. 각 질의는 X1X_1 X2X_2 Y1Y_1 Y2Y_2 WW 형태이며, AA에 다음 연산을 수행하라는 뜻이다.

  • X1≤X2<Y1≤Y2X_1 \le X_2 < Y_1 \le Y_2, X1≤i≤X2X_1 \le i \le X_2, Y1≤j≤Y2Y_1 \le j \le Y_2를 모두 만족하는 정수 쌍 (i,j)(i, j)마다, A[i][j]A[i][j]와 A[j][i]A[j][i]의 값에 WW를 더한다.

정점이 NN개인 무방향 그래프 GG를 생각한다. 각 1≤i,j≤N1 \le i, j \le N에 대해 정점 ii와 jj를 비용 A[i][j]A[i][j]인 간선으로 잇는다. GG의 최소 신장 트리 비용을 구하라.

입력

첫 줄에 정수 NN과 QQ가 주어진다.

이어지는 QQ개의 줄에는 질의를 나타내는 정수 다섯 개 X1X_1 X2X_2 Y1Y_1 Y2Y_2 WW가 한 줄에 하나씩 주어진다.

출력

GG의 최소 신장 트리 비용을 출력한다.

제한

  • 1≤N,Q≤1051 \le N, Q \le 10^5
  • 1≤X1≤X2<Y1≤Y2≤N1 \le X_1 \le X_2 < Y_1 \le Y_2 \le N
  • ∣W∣≤106|W| \le 10^6
  • 시간 제한은 8000 ms, 메모리 제한은 1024 MB이다.

예제3

  1. 예제 1

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

  2. 예제 2

    입력
    5 5
3 3 4 5 -10
1 2 3 4 20
4 4 5 5 -10
2 2 4 4 -20
1 1 2 4 0
    예상 출력
    -20

  3. 예제 3

    입력
    6 8
1 3 6 6 3
4 4 6 6 10
3 3 5 6 -8
1 2 5 5 -7
1 2 6 6 -1
1 3 4 5 6
3 5 6 6 7
2 3 6 6 3
    예상 출력
    -2