Задача
[latex]-[/latex] Печкин, а я научился работать с деревом отрезков. [latex]-[/latex] Заняться тебе нечем просто, Шарик. Лучше бы помог мне письма разносить. [latex]-[/latex] Ну, Печкин, я уже даже выполнил задания Дяди Федора и Кота Матроскина, только этот Матроскин не захотел проверять, правильно ли я сделал. [latex]-[/latex] Ну ладно, давай я проверю, что там надо было сделать? [latex]-[/latex] У меня был массив чисел и множество запросов – представляющих собой либо запрос на изменение в массиве, либо содержащий число, для которого мне нужно было найти такой промежуток [[latex]l;r[/latex]], что максимум на этом промежутке был бы равен заданному числу. Можешь прочитать предыдущую задачу. [latex]-[/latex] Разберемся…Входные данные
В первой строке содержится одно число [latex]N[/latex] ([latex]1≤N≤106[/latex]) – количество элементов в массиве. В следующей строке находится [latex]N[/latex] целых, неотрицательных чисел, не превосходящих 109 – сами элементы массива. Затем следует число [latex]M[/latex] ([latex]1≤M≤105[/latex]) – количество запросов. Затем [latex]М[/latex] строк, первое число в каждой из которых означает тип запроса: если оно равно единице, то далее следует единственное число [latex]x[/latex], и Шарику надо было найти два числа [latex]l[/latex] и [latex]r[/latex], такие, что максимум на промежутке [[latex]l;r[/latex]], был равен [latex]x[/latex]. Если же тип запроса равен двум, то далее следует два числа [latex]pos[/latex] и [latex]val[/latex] и это значит, что элемент массива, стоящий на позиции [latex]pos[/latex], теперь изменен и он стал равен значению [latex]val[/latex]. Далее для каждого запроса с номером один содержится по строке с двумя числами [latex]l[/latex] и [latex]r[/latex] – ответы Шарика.
Выходные данные
Для каждого ответа Шарика выведите [latex]»Yes»[/latex], если он ответил правильно и [latex]»No»[/latex], если Шарик ошибся. Заметьте, что хотя в предыдущей задаче было необходимо найти минимальные числа [latex]l[/latex] и [latex]r[/latex], здесь Печкин проверять этого не будет.
Тесты
Входные данные | Выходные данные |
5 1 2 4 3 1 5 1 4 1 5 2 3 5 1 1 1 4 1 3 1 5 5 5 2 4 |
Yes No Yes No |
Код программы
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 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 |
#include <iostream> using namespace std; template <class POINTER_TYPE, class TYPE> class segment_tree { TYPE *SegmentTree; POINTER_TYPE base_capacity = 0; TYPE (*g)(TYPE, TYPE); TYPE neutral; TYPE result_on_segment_in ( POINTER_TYPE v, POINTER_TYPE tl, POINTER_TYPE tr, POINTER_TYPE l, POINTER_TYPE r ) { if (l > r) return neutral; else if (l == tl && r == tr) return SegmentTree[v]; else { POINTER_TYPE tm = (tl + tr) / 2; return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)), result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r)); } } void make_monoid_and_fill_rest(TYPE *NewTree, const POINTER_TYPE &n, TYPE f(TYPE, TYPE), const TYPE &neutr) { g = f; neutral = neutr; for(POINTER_TYPE i = base_capacity+n; i < 2*base_capacity; ++i) { NewTree[i] = neutral; } for(POINTER_TYPE i = base_capacity-1; i > 0; --i) { NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]); } SegmentTree = NewTree; } void fix_capacity(const POINTER_TYPE &base_array_size) { for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1); } public: void construct(const TYPE *begin, const TYPE *end, TYPE f(TYPE, TYPE), const TYPE neutr) { POINTER_TYPE base_size = end - begin; fix_capacity(base_size); TYPE *NewTree = new TYPE[base_capacity*2]; for(POINTER_TYPE i = 0; i < base_size; ++i) { NewTree[base_capacity+i] = begin[i]; } make_monoid_and_fill_rest(NewTree, base_size, f, neutr); } void read_and_construct(const POINTER_TYPE amount_of_elements, TYPE preprocessing_function(), TYPE f(TYPE, TYPE), const TYPE neutr) { fix_capacity(amount_of_elements); TYPE *NewTree = new TYPE[base_capacity*2]; for(POINTER_TYPE i = 0; i < amount_of_elements; ++i) { NewTree[base_capacity+i] = preprocessing_function(); } make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr); } void assign(const POINTER_TYPE index, const TYPE new_value) { SegmentTree[base_capacity+index] = new_value; for (POINTER_TYPE i = (base_capacity+index)/2; i > 0; i /= 2) { SegmentTree[i] = g(SegmentTree[2*i], SegmentTree[2*i+1]); } } TYPE result_on_segment (POINTER_TYPE l, POINTER_TYPE r) { return result_on_segment_in(1, 0, base_capacity-1, l, r); } }; unsigned int f() { unsigned int X; cin >> X; return X; } unsigned int g(unsigned int a, unsigned int b) { return max(a, b); } int main() { unsigned int n, m; cin >> n; segment_tree <unsigned int, unsigned int> D; D.read_and_construct(n, f, g, 0); cin >> m; unsigned char *type = new unsigned char[m]; unsigned int *a = new unsigned int[m], *b = new unsigned int[m], l, r; for (unsigned int i = 0; i < m; ++i) { cin >> type[i] >> a[i]; if (type[i] == '2') cin >> b[i]; } for (unsigned int i = 0; i < m; ++i) { while (i < m) { if (type[i] == '2') { D.assign(a[i]-1, b[i]); ++i; } else break; } cin >> l >> r; if (i < m) { if (D.result_on_segment(l-1, r-1) == a[i]) cout << "Yes\n"; else cout << "No\n"; } } } |
Решение
Учитывая то, что максимум является ассоциативной операцией, для решения задачи
воспользуемся универсальным деревом отрезков.
Так как во входном потоке сперва идут требуемые результаты максимума на
отрезке, затем модификации отрезка и в конце отрезки, для которых необходимо
совпадение требуемого и реального максимума, то не обойтись без
запоминания/меморизации входных данных.
После этого задача упрощается, и для решения остаётся только пересматривать
все события, и сопоставлять требуемые резальтаты максимума на заданных
отрезках с реальными.
Ссылки
Код на ideone.com
Задача с сайта e-olymp.com.
Засчитанное решение.