https://www.acmicpc.net/problem/3554
위 백준 문제에 대한 번역입니다.
수수께끼의 장치
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 256 MB | 591 | 296 | 229 | 51.810% |
문제
드디어 일어났습니다! 첫 접촉이 이루어졌습니다! 외계인들이 2010년에 지구를 방문할 예정입니다! 그들은 현재 지구의 기술로는 만들 수 없는 수수께끼 같은 장치를 가져올 것을 약속했습니다. 세계의 대부분의 과학자들이 그렇게 생각합니다! 모든 신문사들은 이미 이에 대한 주요 기사를 발행했습니다.
이 장치는 정수 수열 \({a_i}\)를 초기 입력으로 받습니다. 그 후, 다음 두 가지 연산을 수행할 수 있습니다:
- 구간 [l; r]을 선택하고 l ≤ i ≤ r인 모든 \(a_i\)에 대해 \(a_i \leftarrow a_i^2 \bmod 2010\)을 수행합니다.
- 구간 [l; r]을 선택하고 l ≤ i ≤ r인 모든 \(a_i\)의 합을 출력합니다. 주의할 점은 합이 2010으로 나눈 나머지가 아닙니다.
이 장치의 놀라운 점은 50,000개의 숫자로 이루어진 수열에 대해 50,000번의 이러한 연산을 3초 내에 수행할 수 있다는 것입니다. 이전에는 아무도 이렇게 할 수 없었습니다!
하지만 로만은 외계인을 믿지 않으며, 이것이 단지 주식 시장에서 또 다른 백만 달러를 벌기 위해 누군가가 만든 거대한 속임수라고 생각합니다. 그의 목표는 이를 증명하는 것입니다. 그래서 그는 당신을 고용하여 이 장치를 시뮬레이션하는 프로그램을 작성하도록 했습니다.
입력
첫 번째 줄에는 수열의 길이 n이 주어집니다 (1 ≤ n ≤ 50,000).
두 번째 줄에는 초기 수열을 이루는 n개의 숫자 \(a_i\)가 주어집니다 (0 ≤ \(a_i\) ≤ 2009).
세 번째 줄에는 연산의 개수 m이 주어집니다 (1 ≤ m ≤ 50,000).
나머지 파일에는 m개의 줄이 있으며, 각각 하나의 연산을 설명합니다. j번째 연산은 종류 \(k_j\)(제곱은 '1', 합 계산은 '2')와 두 정수 \(l_j\)와 \(r_j\)로 설명됩니다 (1 ≤ \(l_j\) ≤ \(r_j\) ≤ n).
출력
두 번째 종류의 각 연산에 대해 입력에 나타나는 순서대로 각각의 줄에 출력을 작성하십시오.
예제
예제 입력 1
3
17 239 999
4
2 1 3
1 2 3
2 2 3
2 1 2예제 출력 1
1255
1882
858