Logo
(追記) (追記ここまで)

20550번 - 구간 합 구하기 K

시간 제한메모리 제한제출정답맞힌 사람정답 비율
6 초 (하단 참고)512 MB135312223.656%

문제

1~N 범위의 정수 D1, D2, ... , DK 에 대해 정수 V[D1, D2, ... , DK]가 배정되어 있다.

V에 대해 Q개의 쿼리를 처리할 것이고, 쿼리는 2가지 쿼리가 존재한다.

  • 1 S1 E1 S2 E2 ... SKEK : 1이상 K이하를 만족하는 모든 정수 i에 대해서, Ai 값이 Si 이상이면서 Ei 이하를 모두 만족하는 V[A1, A2, ... , AK]들의 합을 출력한다.
  • 2 B1 B2 ... Bk X : V[B1, B2, ... , Bk]를 X로 변경한다.

입력

N, K, Q가 공백을 사이에 두고 한 줄에 주어진다.

2번째 줄에는 V에 배정되어있는 정수 NK개가 주어진다. 2번째 줄의 i번째 수는 V[i // NK-1% N + 1, i // NK-2% N + 1, ..., i // NK-K % N + 1]을 나타낸다. 2번째 줄의 제일 처음 나오는 수는 0번째 수이다. 즉, i는 0부터 시작한다. '//'연산자는 몫 연산자를 의미하고 '%'연산자는 나머지 연산자를 의미하며 '//', '%', '+' 세 연산자의 연산자 우선순위는 같다.

그 다음 Q개의 줄에는 위에 설명된 2개중 하나의 쿼리가 한 줄에 하나씩 주어진다. (1번 쿼리는 최소 한 개 이상 주어진다)

출력

1번 쿼리가 주어졌을 때, 쿼리에 대한 올바른 값을 한 줄에 하나씩 출력한다.

제한

  • 20 ≤ N
  • 1 ≤ K
  • NK ≤ 5×105
  • Q ≤ 105
  • 1 ≤ Si, Ei, Ai,≤ N
  • 0 ≤ V[D1, D2, ... , DK] , X ≤ 105
  • 입력으로 주어지는 모든 수는 정수이다.

예제 입력 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

예제 출력 1 

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

예제 출력 2 

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

예제 출력 3 

342
393
342
380
384
390

힌트

출처

University > 인하대학교 > 2020 인하대학교 프로그래밍 경진대회 (IUPC) L번

시간 제한

  • Java 8: 8 초
  • Java 8 (OpenJDK): 8 초
  • Java 11: 8 초
  • Kotlin (JVM): 8 초
  • Java 15: 8 초
(追記) (追記ここまで)

출처

대학교 대회

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

AltStyle によって変換されたページ (->オリジナル) /