구간 합 구하기 K

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

요약

K차원 배열에서 각 차원의 구간에 속한 값들의 합을 구하고, 한 칸의 값을 바꾸는 문제입니다.

난이도: 보통10점 중 5점
유형: 누적 합, 배열
정답자: 아직 제출이 없습니다

문제

$1$ 부터 $N$ 까지 범위의 정수 $D_1, D_2, \ldots, D_K$ 에 대해 정수 $V[D_1, D_2, \ldots, D_K]$ 가 배정되어 있다.

$V$ 에 대해 $Q$ 개의 쿼리를 처리한다. 쿼리는 두 종류다.

첫 번째 쿼리는 1 S_1 E_1 S_2 E_2 ... S_K E_K이다. $1$ 이상 $K$ 이하의 모든 정수 $i$ 에 대해 $A_i$ 값이 $S_i$ 이상 $E_i$ 이하인 $V[A_1, A_2, \ldots, A_K]$ 의 합을 출력한다.

두 번째 쿼리는 2 B_1 B_2 ... B_K X이다. $V[B_1, B_2, \ldots, B_K]$ 를 $X$ 로 바꾼다.

입력

첫째 줄에 $N$ , $K$ , $Q$ 가 공백으로 구분되어 주어진다.

둘째 줄에는 $V$ 에 배정된 정수 $N^K$ 개가 주어진다. 둘째 줄의 $i$ 번째 수(0부터 시작)는 V[i // N^(K-1) % N + 1, i // N^(K-2) % N + 1, ..., i // N^0 % N + 1] 위치에 배정된 값이다. //는 몫, %는 나머지 연산자이며, //, %, +의 우선순위는 같다.

그 다음 $Q$ 개의 줄에는 위에서 설명한 두 쿼리 중 하나가 한 줄에 하나씩 주어진다. 첫 번째 쿼리는 최소 한 개 이상 주어진다.

출력

첫 번째 쿼리마다 정답을 한 줄에 하나씩 출력한다.

제한

$20 \le N$
$1 \le K$
$N^K \le 5 \times 10^5$
$Q \le 10^5$
$1 \le S_i, E_i, A_i \le N$
$0 \le V[D_1, \ldots, D_K], X \le 10^5$
입력으로 주어지는 모든 수는 정수이다.

예제3

예제 1

입력

20 1 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 20
2 1 10
1 1 20

예상 출력

20
29

예제 2

입력

20 2 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 20 1 20
2 1 1 30
1 1 20 1 20

예상 출력

400
429

예제 3

입력

20 2 20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 2 20 2 19
2 5 14 7
2 12 9 8
1 1 20 2 20
2 18 1 3
2 14 17 6
1 2 19 2 19
2 13 8 8
2 20 8 3
2 7 1 1
2 13 13 6
2 8 16 2
2 10 19 6
1 2 19 1 19
2 12 16 5
2 17 2 3
1 2 19 2 20
2 3 3 2
2 6 12 4
1 2 20 2 19

예상 출력