Задача e-olimp 695.
Последовательность [latex]a_{n}[/latex] задается следующей формулой: [latex]a_{n}=n^{2} mod 12345+n^{3} mod 23456[/latex].
Требуется много раз отвечать на запросы следующего вида:
- найти разность между максимальным и минимальным значением среди элементов [latex]a_{i},a_{i+1}, …,a_{j}[/latex];
- присвоить элементу [latex]a_{i}[/latex] значение [latex]j[/latex].
Технические условия.
Входные данные
Первая строка содержит натуральное число [latex]k (k\leq 100000)[/latex] — количество запросов. Следующие [latex]k[/latex] строк содержат запросы, по одному в строке. Запрос номер [latex]i[/latex] описывается двумя целыми числами [latex]x_{i},y_{i}[/latex].
Если [latex]x_{i}>0[/latex], то требуется найти разность между максимальным и минимальным значением среди элементов [latex]a_{x_{i}}…a_{y_{i}}[/latex]. При этом [latex]1\leq x_{i}\leq y_{i}\leq 100000[/latex].
Если [latex]x_{i}<0[/latex], то требуется присвоить элементу [latex]a_{-x_{i}}[/latex] значение[latex]y_{i}[/latex]. При этом[latex]-100000\leq x_{i}\leq 1[/latex] и [latex]\left | y_{i} \right |\leq 100000[/latex].
Выходные данные
Для каждого запроса первого типа требуется вывести в отдельной строке разность между максимальным и минимальным значением на соответствующем отрезке.
Пример.
| Пример входных данных | Пример выходных данных |
| 7
1 3 2 4 -2 -100 8 9 -3 -101 2 3 |
34
68 250 234 1 |
Решение.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <iostream> #include <math.h> #include <algorithm> #include <climits> using namespace std; #define length 100000 int main() { int a[length]; for(long long i=1;i<=length;i++) { a[i-1]=((i%12345)*(i%12345))%12345+((i%23456)*(i%23456)%23456*i%23456)%23456; //заполнение массива } int k,x,y,result; cin>>k; int mmax,mmin; //переменные для хранения максимума и минимума на отрезке for(int i=0;i<k;i++) { cin >> x >> y; mmax=INT_MIN; mmin=INT_MAX; if(x>0) { for(int i=x-1;i<y;i++) //поиск максимума и минимума на отрезке [x,y] { if(mmax<a[i]) mmax=a[i]; if(mmin>a[i]) mmin=a[i]; } cout << mmax-mmin << endl; } else { x*=-1; a[x-1]=y; //замена x-го элемента на y } } } |
Так как количество запросов [latex]k\leq 100000[/latex] сначала считаем значение всех элементов последовательности и сохраняем их в массив. Если требуется найти разность между максимумом и минимумом,то находим их проверяя все элементы отрезка и выводим разность. Если требуется заменить элемент, то заменяем соответствующий элемент последовательности на новый.
Ссылка на засчитанное решение.
В скором времени будет добавлено более эффективное решение с помощью дерева отрезков.