Условие
Задача взята отсюда.
Последовательность [latex]a_n[/latex] задается следующей формулой: [latex]a_n = n^2 \mod 12345 + n^3 \mod 23456[/latex].
Требуется много раз отвечать на запросы следующего вида:
- найти разность между максимальным и минимальным значением среди элементов [latex]a_i, a_{i+1}, \ldots, a_j[/latex];
- присвоить элементу [latex]a_i[/latex] значение [latex]j[/latex].
Входные данные
Первая строка содержит натуральное число [latex]k[/latex] [latex](k \leq 10^5)[/latex] — количество запросов. Следующие [latex]k[/latex] строк содержат запросы, по одному в строке. Запрос номер [latex]i[/latex] описывается двумя целыми числами [latex]x_i[/latex], [latex]y_i[/latex].
Если [latex]x_i > 0[/latex], то требуется найти разность между максимальным и минимальным значением среди элементов [latex]a_{xi}, a_{xi+1}, \ldots, a_{yi}[/latex]. При этом [latex]1 \leq x_i \leq y_i \leq 10^5[/latex].
Если [latex]x_i < 0[/latex], то требуется присвоить элементу [latex]a_{-xi}[/latex] значение [latex]y_i[/latex]. При этом [latex]-10^5 \leq x_i \leq 1[/latex] и [latex]|y_i| \leq 10^5[/latex].
Выходные данные
Для каждого запроса первого типа требуется вывести в отдельной строке разность между максимальным и минимальным значением на соответствующем отрезке.
Тесты
| № | Входные данные | Выходные данные |
| 1 | 7 1 3 2 4 -2 -100 1 5 8 9 -3 -101 2 3 |
34 68 250 234 1 |
| 2 | 4 1 100000 100000 100000 -100000 42000 1 100000 |
35753 0 41998 |
| 3 | 13 1 17 -5 -400 -3 500 3 5 1 17 -2 345 2 345 2 3 2 5 -1 -100000 -2 100000 1 2 1 100000 |
5200 900 5602 35813 155 900 200000 200000 |
Код
|
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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
#include <iostream> #include <utility> #include <algorithm> #define SIZE 100000 using namespace std; void build(pair<int, int>* tree, int pos, int l, int r) { if (l == r) { tree[pos].first = (l % 12345) * (l % 12345) % 12345 + ((l % 23456) * (l % 23456) % 23456) * (l % 23456) % 23456; tree[pos].second = tree[pos].first; } else { int m = (l + r) / 2; build(tree, pos * 2, l, m); build(tree, pos * 2 + 1, m + 1, r); tree[pos] = make_pair(max(tree[pos * 2].first, tree[pos * 2 + 1].first), min(tree[pos * 2].second, tree[pos * 2 + 1].second)); } } pair<int, int> get(pair<int, int>* tree, int pos, int l, int r, int ql, int qr) { if (l == ql && r == qr) return tree[pos]; else { int m = (l + r) / 2; if (qr <= m) return get(tree, pos * 2, l, m, ql, qr); else if (ql >= m + 1) return get(tree, pos * 2 + 1, m + 1, r, ql, qr); else { pair<int, int> a = get(tree, pos * 2, l, m, ql, m); pair<int, int> b = get(tree, pos * 2 + 1, m + 1, r, m + 1, qr); return make_pair(max(a.first, b.first), min(a.second, b.second)); } } } void modify(pair<int, int>* tree, int pos, int l, int r, int npos, int nv) { if (l == r) { tree[pos].first = nv; tree[pos].second = nv; } else { int m = (l + r) / 2; if (npos <= m) modify(tree, pos * 2, l, m, npos, nv); else modify(tree, pos * 2 + 1, m + 1, r, npos, nv); tree[pos] = make_pair(max(tree[pos * 2].first, tree[pos * 2 + 1].first), min(tree[pos * 2].second, tree[pos * 2 + 1].second)); } } int main() { ios::sync_with_stdio(false); pair<int, int> tree[SIZE * 4]; build(tree, 1, 1, SIZE); int n, x, y; cin >> n; for (int i = 0; i < n; i++) { cin >> x >> y; if (x > 0) { pair<int, int> query = get(tree, 1, 1, SIZE, x, y); cout << query.first - query.second << endl; } else modify(tree, 1, 1, SIZE, -x, y); } return 0; } |
Решение
Задача решается с помощью стандартного Дерева Отрезков (подробно про ДО прочитать можно, например, на сайте Е-maxx, ссылка ниже). Отметим особенности построения данного дерева. В вершинах дерева хранить будем не по одному, а по два значения — соответственно максимум и минимум на отрезке. Тогда при построении дерева, спускаясь до листа, будем считать элемент последовательности по формуле, данной в условии, и это значение будет как минимумом, так и максимум для отрезка из одного элемента. Для остальных элементов имеем:
|
1 |
tree[pos] = make_pair(max(tree[pos * 2].first, tree[pos * 2 + 1].first), min(tree[pos * 2].second, tree[pos * 2 + 1].second)); |
Где элементы с номерами [latex]pos * 2[/latex] и [latex]pos * 2 + 1[/latex] — левый и правый потомок соответственно. Для удобства, дерево нумеруется с единицы.
Функция подсчета на отрезке ни чем не отличается от стандартной. Если интервалы запроса совпадают с интервалами отрезка, возвращаем значение на этом отрезке (значение в вершине, которая за него отвечает). Если ответ лежит целиком в левом/правом подотрезке, вызываем рекурсивно функцию с соответствующими концами отрезка и вершиной дерева. Если ответ не лежит целиком ни в левом, ни в правом подотрезке, а находится частично в них обоих, то в качестве максимума берем максимальное значение из максимумов подотрезков, для минимума — аналогично.
Функция обновления рекурсивно спускается от корня до соответствующего элемента, меняя его значение, а потом обновляет значения всех вершин, для которого этот элемент является подотрезком, в направлении от элемента до корня (формула пересчета та же, что использовалась при построении дерева).
Таким образом, в самой программе мы просто строим дерево, а потом в цикле отвечаем на запросы, выполняя необходимые действия (как описано в условии). При запросе типа [latex]1[/latex] [latex](x_i > 0)[/latex] выводим разницу между полученными максимумом и минимумом.
Ссылки
Ваша программа работает в ldf раза быстрее, чем вариант ниже. Правда тратит вчетверо больше памяти.