문제 https://codeforces.com/problemset/problem/276/C 풀이 크기 n인 수열 a와 쿼리 q개가 주어진다. 각 쿼리는 인덱스 $[l, r]$ 범위를 지정하며, 해당 범위의 원소 합을 구한다. 수열 a를 적절히 재배열하여 모든 쿼리의 합의 총합을 최대화 한 수를 출력하면 된다. 쿼리가 여러번 나오고 어떤 원소들은 쿼리 안에 중복되어서 포함되어 있을 수 있다. 쿼리의 범위 안에 가장 많이 포함된 원소의 순서대로, 높은 값을 배치하는 정렬 문제로 환원된다. 어떤 원소 $a_i$가 쿼리 내부에 포함되어 있는지를 일반적으로 판단하게 되면 $O(q \times n)$이 되는데, q, n의 범위가 $1 \leq q 2 \times 10^5$ 이므로, 시간 안에 문제를 해결하기 어려워진다. ...
문제 https://leetcode.com/problems/concatenate-non-zero-digits-and-multiply-by-sum-ii 풀이 1번 문제와 로직은 동일하다. 차이점은 스트링 s의 서브스트링에 같은 작업을 queries마다 반복해야 한다는 점이다. queries의 원소가 최대 10만 개이므로, 매 쿼리마다 부분 문자열을 슬라이싱해서 처리하면 시간 초과가 난다. 따라서 전처리를 통해 각 쿼리를 $O(1)$ 혹은 $O(n \log n)$에 처리할 수 있도록 해야 한다. 전처리 단계에서 네 가지 누적 배열을 만든다. pow10: $\text{pow10}[i] = 10^i \mod (10^9 + 7)$ preSum: 각 인덱스까지 자릿수의 합 preConcat: 각 인덱스까지 0이 아닌 숫자들을 이어붙인 값 nonZeroCount: 각 인덱스까지 0이 아닌 숫자의 개수 쿼리 [l, r]이 들어오면 네 배열로 x와 sum을 $O(1)$에 구해 $x \times \text{sum} \mod (10^9 + 7)$를 리턴한다. 0이 아닌 숫자가 없는 경우는 수식이 자연스럽게 $0$을 리턴하게 된다. ...