백준3554🐨Enigmatic Device

https://www.acmicpc.net/problem/3554

 위 백준 문제에 대한 번역입니다.

외계인의 신비한 장치

시간 제한: 3초, 메모리 제한: 256MB

문제 설명:
드디어 일어났습니다! 첫 접촉이 이루어졌습니다! 외계인들이 2010년에 지구를 방문할 예정이며, 현재 지구 기술로는 만들 수 없는 신비한 장치를 가져오기로 약속했습니다. 대부분의 세계 과학자들이 그렇게 생각하고 있으며, 모든 신문사들이 이미 이에 대한 주요 기사를 발표했습니다.

이 장치는 초기 입력으로 정수 수열 $\{a_i\}$를 받아들입니다. 그 후, 다음 두 가지 연산을 수행할 수 있습니다:

1. 구간 $[l; r]$을 선택하고, $l \le i \le r$ 인 모든 $a_i$에 대해 $a_i \leftarrow a_i^2 \bmod 2010$ 연산을 수행합니다.
2. 구간 $[l; r]$을 선택하고, $l\le i \le r$ 인 모든 $a_i$의 합을 출력합니다. 주의: 이 합은 2010으로 나눈 나머지가 아닙니다.

이 장치의 놀라운 점은 $50\,000$개의 숫자로 이루어진 수열에 대해 이러한 종류의 연산을 $50\,000$번 3초 안에 수행할 수 있다는 것입니다. 이전에는 누구도 이런 일을 할 수 없었습니다!

하지만 로만은 외계인을 믿지 않으며, 이것이 단지 주식 시장에서 또 다른 백만 달러를 벌기 위해 누군가가 만든 큰 사기라고 생각합니다. 그의 목표는 이를 증명하는 것입니다. 그래서 그는 당신을 고용해 이 장치를 시뮬레이션하는 프로그램을 작성하도록 했습니다.

정수 수열 $a_i$와 연산 순서가 주어졌을 때, 이 이상한 외계인 장치의 동작을 시뮬레이션하는 프로그램을 작성하세요.

입력:
첫 번째 줄에는 수열의 길이 $n$이 주어집니다 $(1 \le n \le 50\,000)$.
두 번째 줄에는 초기 수열을 구성하는 $n$개의 숫자 $a_i$가 주어집니다 $(0 \le a_i \le 2009)$.
세 번째 줄에는 연산의 수 $m$이 주어집니다 $(1 \le m \le 50\,000)$.
나머지 줄에는 $m$개의 줄에 걸쳐 각 연산이 설명됩니다. $j$번째 연산은 종류 $k_j$ (제곱 연산은 '1', 합 계산은 '2'), 그리고 두 정수 $l_j$와 $r_j$ $(1 \le l_j \le r_j \le n)$로 설명됩니다.

출력:
두 번째 종류의 각 연산에 대해, 입력에 나타난 순서대로 각각의 출력을 별도의 줄에 작성하세요.

예제 입력 1:
3
17 239 999
4
2 1 3
1 2 3
2 2 3
2 1 2

예제 출력 1:
1255
1882
858

출처:
ICPC > Regionals > Northern Eurasia > North-Western Russia Regional Contest > NEERC Northern Subregional 2009 E번

알고리즘 분류:
* 구현