Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1260. Enigmatic Device
Дерево отрезков, декартово дерево, √-декомпозицияОлимпиадные задачи на английском языке
| 03/11/2009 | Тренировка (задачи Северного четвертьфинала 2009) (E) |
| 17/07/2020 | Летние сборы - 9 (командное) (E) |
Ограничения: время – 3s/6s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Yes, it happened! The first contact! Aliens will visit the Earth in 2010!
And they promised to bring an enigmatic device which cannot be constructed
using existing Earth technologies. Most of the scientists of the world think so!
All newspapers already published their leading articles about it.
This device will accept an integer sequence {`a_i`} as its initial input.
After that, it can perform the following two operations:
- Take an interval `[l;\ r]` and perform `a_i\ ←\ a_i^2\ mod\ 2010` for all `a_i` such that `l\ ≤\ i\ ≤\ r`.
- Take an interval `[l;\ r]` and output the sum of all `a_i` such that `l\ ≤\ i\ ≤\ r`. Note that the sum is not taken modulo 2010.
The amazing thing about this device is that it is able to perform `50\ 000`
operations of this kind with a sequence of `50\ 000` numbers within 3 seconds.
Nobody could do it before!
But Roman does not believe in aliens and thinks that it is only a great hoax
made by somebody just to win another million bucks on the stock exchange.
His goal is to prove this. So he hired you to write a program to simulate this device.
Given an integer sequence `a_i` and a sequence of operations, write a program
which simulates the behaviour of the strange alien device.
Input
The first line of the input contains the length of the sequence `n` (`1\ ≤\ n\ ≤\ 50\ 000`).
The second line contains `n` numbers `a_i` forming the initial sequence
(`0\ ≤\ a_i\ ≤\ 2009`). The third line contains the number of operations `m`
(`1\ ≤\ m\ \ ≤\ 50\ 000`). The rest of file contains `m` lines, each describing one
operation. The `j`-th operation is described by its kind `k_j` ('1' for
squaring, '2' for calculating the sum), followed by two integers `l_j` and `r_j` (`1\ ≤\ l_j\ ≤\ r_j\ ≤\ n`).
Output
For each operation of the second kind, write their output on the separate
line, in order they appear in the input.
Sample Input
3 17 239 999 4 2 1 3 1 2 3 2 2 3 2 1 2
Sample Output
1255 1882 858
