페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#2484

[중등부] 2025 KOI 1차대회 대비 모의고사 (1주차)

자릿수 합 쿼리
서브태스크
1초 512MB

문제

길이 N의 수열 A_1, A_2, \dots, A_N​이 주어진다. 이 수열에 대해 총 Q개의 쿼리를 처리해야 한다. 쿼리는 아래 두 종류이다.

  1. 변환 쿼리:1 L R
    구간 [L, R]의 각 인덱스 i (1 \le i \le N)에 대하여, 만약 A_i​가 두 자리 이상의 수(즉, A_i \ge 10)라면 A_i​를 자릿수 합으로 변환한다.
    자릿수 합 함수 f(x)는 x의 십진수 자릿수를 모두 더한 값이다. (예: f(1234)=1+2+3+4=10)
    주의: 한 번의 변환 쿼리에서는 각 해당 인덱스에 대해 변환을 최대 한 번만 적용한다. 즉, 합이 두 자리 이상의 수여도 다시 계산하지 않는다.

  2. 합 쿼리:2 L R
    현재 수열의 구간 [L,R]에 있는 원소들의 합을 출력한다.


입력

첫 줄에 정수 N과 Q가 주어진다. (1 \le N, Q \le 200\,000)

둘째 줄에 N개의 정수 A_1, A_2, \dots, A_N이 공백으로 구분되어 주어진다. (1 \le A_i \le 10^{13})

이후 Q개의 줄에 걸쳐 쿼리가 주어진다. 각 쿼리는 두 형식 중 하나이다.

  • 변환 쿼리:1 L R (1 \le L \le R \le N)

  • 합 쿼리:2 L R (1 \le L \le R \le N)


출력

합 쿼리(2 L R)에 대해, 해당 구간의 원소 합을 한 줄에 하나씩 출력한다.


부분문제

번호 점수 조건
#130점

1 \le N, Q \le 100

#230점

변환 쿼리:1 L R에 대하여 R - L \le 100인 데이터만 주어짐

#340점

추가 제약 조건 없음


예제 

5 5
123 99 5 18 10
2 1 5
1 1 3
2 1 5
1 1 5
2 1 5
255
57
30

초기 수열: [123, 99, 5, 18, 10]


합 쿼리 2 1 5:

  • 123 + 99 + 5 + 18 + 10 = 255 출력.

변환 쿼리 1 1 3:

  • A_1 = 123 \rightarrow f(123)=6

  • A_2 = 99 \rightarrow f(99)=18

  • A_3 = 5 (한 자릿수이므로 그대로)

  • 업데이트 후 수열: [6, 18, 5, 18, 10]

합 쿼리 2 1 5:

  • 6 + 18 + 5 + 18 + 10 = 57 출력.

변환 쿼리 1 1 5:

  • A_1 = 6 (한 자릿수)

  • A_2 = 18 \rightarrow f(18)=9

  • A_3 = 5

  • A_4 = 18 \rightarrow f(18)=9

  • A_5 = 10 \rightarrow f(10)=1

  • 업데이트 후 수열: [6, 9, 5, 9, 1]

합 쿼리 2 1 5:

  • 6 + 9 + 5 + 9 + 1 = 30 출력.

로그인해야 코드를 작성할 수 있어요.