e-olymp 4493. Трое из Простоквашино 3

Задача

[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

Код программы

Решение

Учитывая то, что максимум является ассоциативной операцией, для решения задачи
воспользуемся универсальным деревом отрезков.
Так как во входном потоке сперва идут требуемые результаты максимума на
отрезке, затем модификации отрезка и в конце отрезки, для которых необходимо
совпадение требуемого и реального максимума, то не обойтись без
запоминания/меморизации входных данных.
После этого задача упрощается, и для решения остаётся только пересматривать
все события, и сопоставлять требуемые резальтаты максимума на заданных
отрезках с реальными.

Ссылки
Код на ideone.com
Задача с сайта e-olymp.com.
Засчитанное решение.

e-olymp 4496. Приключение Незнайки и его друзей

Задача с сайта e-olymp.com.

Условие задачи

Все мы помним историю о том, как Незнайка со своими друзьями летали на воздушном шаре путешествовать. Но не все знают, что не все человечки влезли в шар, так как у него была ограниченная грузоподъемность.

В этой задаче Вам необходимо узнать, сколько же человечков улетело путешествовать. Известно, что посадка в шар не является оптимальной, а именно: человечки садятся в шар в той очереди, в которой они стоят, как только кому-то из них не хватает места, он и все оставшиеся в очереди разворачиваются и уходят домой.

Входные данные

В первой строке содержится количество человечков [latex]n (1 ≤ n ≤ { 10 }^{ 6 })[/latex] в цветочном городе. Во второй строке заданы веса каждого из человечков в том порядке, в котором они будут садиться в шар. Все веса натуральные числа и не превышают [latex]{ 10 }^{ 9 }[/latex]. Далее следует количество запросов [latex]m (1 ≤ m ≤ { 10 }^{ 5 })[/latex]. Каждый запрос представляет собой одну строку. Если первое число в строке равно единице, то далее следует еще одно число [latex]v (1 ≤ v ≤ { 10 }^{ 9 })[/latex] – грузоподъемность воздушного шара. Если же оно равно двум, то далее следует два числа [latex]x (1 ≤ x ≤ n)[/latex] и [latex]y (1 ≤ y ≤ { 10 }^{ 9 })[/latex] — это значит, что вес человечка, стоящего на позиции [latex]x[/latex], теперь равен [latex]y[/latex].

Выходные данные

Для каждого запроса с номером один выведите в отдельной строке количество человечков, поместившихся в шар.

Тесты

Входные данные Выходные данные
1 5
1 2 3 4 5
5
1 7
1 3
2 1 5
1 7
1 3
3
2
2
0
2 2
1 2
3
1 4
2 1 10
1 4
2
0
3 2
999999999 1000000000
4
1 999999999
2 1 1000000000
1 999999999
1 1000000000
1
0
1

Код программы

Описание

В данной задаче требуется эффективно выполнять две операции: изменять значение одного из элементов массива и находить, сколько человечков поместится в шар при заданной грузоподъёмности. Это было реализовано при помощи структуры segment_tree. В функции main сначала вводится значение n и заполняется массив весов человечков weights, после чего по нему выполняется построение дерева отрезков tr. В его вершинах хранятся частичные суммы элементов массива. Да и в целом функции для построения и выполнения запроса модификации у него такие же, как и у обычного дерева отрезков для нахождения суммы на отрезке. Для удобства в массиве weights и в самом дереве используются элементы с первого по [latex]n[/latex]-й, а не с нулевого по [latex]\left( n-1 \right) [/latex]-й. Далее в ходе работы функции main в цикле выполняется обработка запросов. Сначала вводится тип запроса type. Если запрос второго типа, вводятся позиция человечка x, его новый вес y и вызывается метод update, пересчитывающий значения суммы в вершинах, на которые влияет это изменение. Иначе вводится грузоподъемность воздушного шара v и вызывается метод find_numb_of_p, который находит количество человечков, поместившихся в шар. Работает он следующим образом: если выполняется условие tree_l == tree_r, значит, рассматриваемый отрезок состоит из одного элемента, и функция возвращает [latex]1[/latex], если человечек может поместиться в шар, и [latex]0[/latex], если он слишком тяжёлый. Если отрезок больше, вычисляется индекс элемента, находящегося посередине tree_m. Далее, если сумма весов человечков в левом поддереве tree[v*2] больше, чем грузоподъёмность шара, то никто из правого поддерева уже не поместится, и искать следует только в левом поддереве. Иначе в шар следует посадить всех человечков из левого поддерева (их количество равно tree_m - tree_l + 1) и посмотреть, сколько поместится человечков из правого поддерева. При этом необходимо от максимально допустимого веса отнять вес человечков из левого поддерева, уже сидящих в шаре ( max_w-tree[v*2]).

Код на ideone.com.
Засчитанное решение на e-olymp.com.
При решении задачи был использован материал с сайта e-maxx.ru.

e-olymp 3358. Чёрный ящик

Задача

В черный ящик кладутся листки с написанными на них числами. На каждом листке — ровно одно целое число. Иногда некоторые листки исчезают из ящика. После каждого события (когда в ящик положили листок, или когда из ящика исчез листок), нужно вывести число, которое встречается чаще всего на листках, находящихся в данный момент в ящике. Если таких чисел несколько, выведите наименьшее.

Входные данные

Первая строка содержит количество событий [latex]n[/latex] [latex]\left(1 \le n \le 2 \times 10^{5} \right)[/latex]. Каждая из следующих n строк содержит описание одного события:

  • [latex]+ x[/latex] — положен листок с числом [latex]x[/latex] [latex]\left(1 \le x \le 10^{6} \right)[/latex];
  • [latex]- x[/latex] — исчез листок с числом [latex]x[/latex] (гарантируется, что в ящике был хотя бы один листок с числом [latex]x[/latex]).

Выходные данные

Вывести в точности [latex]n[/latex] строк — по одной для каждого события. Каждая строка должна содержать одно число — ответ к задаче. Если после какого-то события ящик оказался пуст, следует вывести [latex]0[/latex].

Тесты

Входные данные Выходные данные
3
+ 1
— 1
+ 2
1
0
2
6
+ 1
+ 1000000
— 1
+ 4
+ 4
— 1000000
1
1
1000000
4
4
4
8
+ 71
+ 91
+ 99
+ 71
— 71
— 91
— 71
— 99
71
71
71
71
71
71
99
0

Код программы

Решение задачи

Проанализируем задачу: так как требуется вывести число, которое встречается чаще всего на листках, находящихся в ящике после запроса удаления/добавления, а если таких чисел несколько, то вывести наименьшее, то задачу можно переформулировать следующим образом:

«Даётся последовательность (массив) объектов leaf [latex]x_{1}[/latex], [latex]x_{2}[/latex], [latex]x_{3}[/latex], [latex]\ldots[/latex], [latex]x_{999999}[/latex], [latex]x_{1000000}[/latex], представляющих из себя пару (number, amount)[latex]=x_{i}=\left(i, a_{i}\right) \in {\mathbb{N}_{0}}^{2}[/latex], где первые элементы пар [latex]i[/latex] представляет из себя число/номер листка, а вторые элементы [latex]a_{i}[/latex] — число листков с этим номером. Изначально все элементы пар [latex]a_{i}[/latex] равны нулю (так как изначально ящик пуст). Для запросов первого типа [latex]+ x[/latex] необходимо увеличивать на единицу число [latex]a_{i}[/latex] объекта, у которого номер [latex]i[/latex] равен [latex]x[/latex], а для запросов второго типа — уменьшать. Для каждого запроса необходимо вывести число [latex]j[/latex], удовлетворяющее условию [latex]j = \min\limits_{i \in \mathbb{K}}{i}[/latex], где [latex]\mathbb{K} = \{i \mid a_{i} = \max\limits_{k \in \{1, 2, \ldots, 1000000\}}{a_{k}} \}[/latex]».

Иными словами, число [latex]i[/latex] соответствует некоторому элементу [latex]x_{i} = \left(i, a_{i}\right)[/latex], который в свою очередь определяется операцией такой, что [latex]i[/latex] и [latex]a_{i}[/latex] удовлетворяют приведённым выше условиям. Очевидно, что данная операция является ассоциативной (как объединение минимума и максимума на заданных множествах), а потому для решения задачи воспользуемся универсальным деревом отрезков.

Создадим дерево отрезков box методом read_and_construct из объектов leaf. Так как нумерация листков начинается с единицы, а их число не превышает [latex]10^{6}[/latex], зададим размер базы дерева отрезков [latex]10^{6}+1[/latex], добавив неё элемент с индексом [latex]0[/latex]. Модифицируем метод read_and_construct таким образом, чтобы в функцию-препроцессор передавался номер элемента [latex]i[/latex], дабы была возможность задавать элементам [latex]x_{i}[/latex] их первоначальные значения [latex]\left(i, 0\right)[/latex]. Вышеупомянутую операцию назовём max_leafs и определим таким образом, чтобы она принимала два аргумента [latex]x_{i} = \left(i, a_{i}\right)[/latex] и [latex]x_{j} = \left(j, a_{j}\right)[/latex] и возвращала тот из них, у которого значение [latex]a[/latex] является большим, а в случае равенства этих значений — аргумент с меньшим индексом. Нейтральным элементом относительно данной операции будет, очевидно, пара [latex]\left(+\infty, 0\right)[/latex], но в силу того, что номера элементов не превышают [latex]10^6[/latex], вместо неё мы будем пользоваться парой [latex]\left(2 \times 10^{6}, 0\right)[/latex].

Далее при запросах вида [latex]+ x[/latex] будем увеличивать соответствующее значение [latex]a_{x}[/latex] пары [latex]\left(x, a_{x}\right)[/latex] на единицу, а при запросах вида [latex]- x[/latex] — уменьшать. Для обоих запросов будем выводить номер заданного листка, который удовлетворяет приведённым в задаче условиям, с использованием метода result_on_segment на всём отрезке [latex]\left[0, 10^{6}\right][/latex]. Ответом для каждого запроса будет значение number пары, которую вернёт метод.

Примечание: ситуация когда ящик становится пустым нигде не обрабатывается, но в силу того, что мы определили массив на отрезке [latex]\left[0, 10^{6}\right][/latex] вместо [latex]\left[1, 10^{6}\right][/latex] в нём всегда есть пара [latex]\left(0, 0\right)[/latex] (листки с номером [latex]0[/latex], число (значение [latex]b[/latex]) которых всегда равно [latex]0[/latex] в силу того, что листки с номером [latex]0[/latex] в ящик не добавляются). Так как определённая нами операция всегда возвращает минимальный номер листка, число которого максимально, то в случае, когда ящик пуст (т.е. значения всех [latex]a_{i} = 0, i = 0, 1, \ldots, 10^{6}[/latex]) будет выводится номер листка [latex]0[/latex]. Этот побочный эффект данного нами определения массива решает эту ситуацию и завершает решение задачи.

Ссылки

Универсальное дерево отрезков

Некоторые теоретические сведения

Обобщённое условие задач на дерево отрезков, как правило, выглядит так:
«Пусть дан моноид [latex]\left(\mathbb{G}, \circ\right)[/latex], где [latex]\mathbb{G}[/latex] — некоторое непустое множество, [latex]\circ[/latex] — ассоциативная бинарная алгебраическая операция на этом множестве, имеющая нейтральный элемент, [latex]A[/latex] — последовательность (массив) элементов из [latex]\mathbb{G}[/latex], содержащая [latex]n[/latex] элементов ([latex]n \in \mathbb{N}[/latex]; с математической точки зрения [latex]A[/latex] — вектор, построенный из элементов [latex]\mathbb{G}[/latex], или [latex]А = \left( x_{0}, x_{1}, \ldots, x_{n-1} \right) \in \mathbb{G}^{n}[/latex]).
Даётся [latex]m[/latex] ([latex]m \in \mathbb{N}[/latex]) запросов двух типов:
1) вычислить значение выражения [latex]x_{i} \circ x_{i+1} \circ \ldots \circ x_{j-1} \circ x_{j}[/latex] с заданными [latex]i[/latex], [latex]j[/latex] ([latex]0 \le i \le j \le n-1[/latex], [latex]i, j \in \mathbb{N} \cup \{ 0 \}[/latex]) и вывести его;
2) заменить значение элемента с индексом [latex]k[/latex] на [latex]y[/latex] ([latex]k \in \mathbb{N} \cup \{ 0 \}[/latex], [latex]k \le n-1[/latex], [latex]y \in \mathbb{G}[/latex]).»

Как правило, человек, впервые увидевший задачу подобного рода, решает её следующим образом: для запросов первого типа (далее — запросы значения на отрезке [latex]\left[i, j\right][/latex]) создаётся вспомогательная переменная, изначально равная нейтральному элементу моноида (к примеру, если [latex]\left( \mathbb{G}, \circ \right) = \left( \mathbb{Z}, + \right)[/latex] то нейтральным элементом относительно [latex]+[/latex] является [latex]0[/latex]), и запускается цикл на заданном отрезке, который «прибавляет» к ней новые «слагаемые», а обработка запросов из пункта 2 реализуется через простое присваивание элементу массива с заданным индексом [latex]i[/latex] значения [latex]y[/latex]. Таким образом вычислительная сложность запросов замены составляет [latex]O\left(1\right)[/latex], а запросов поиска значения на отрезке [latex]\left[i, j\right][/latex] в лучшем случае составляет [latex]O\left(1\right)[/latex], когда [latex]i = j[/latex], а в худшем [latex]O\left(n\right)[/latex], когда [latex]i = 0[/latex], [latex]j = n-1[/latex].

Дерево отрезковструктура данных, которая позволяет сбалансировать операции замены и вычисления значения на заданном отрезке до вычислительной сложности [latex]O\left(\log_{2}{n}\right)[/latex] и значительно улучшить общую сложность программы с [latex]O\left(n+n\cdot m\right) = O\left(n\cdot m\right)[/latex] до [latex]O\left(n+m\cdot\log_{2}{n}\right)[/latex].

Определение: массив/последовательность элементов/вектор, над которым построено дерево отрезков, называется базой дерева или просто базой, а число её элементов — её размерностью.

Задача 1: единичная модификация

Написать класс «дерево отрезков», применимый к любой задаче на моноиде, в которой присутствуют запросы замены элемента и результата операции на отрезке,
и таблицу его базовых функций и параметров.

Код класса

Описание класса

Далее [latex]n[/latex] — размерность базы дерева.

Название объекта Описание
Параметр
TYPE Тип объектов дерева, над которыми будут проводится вычисления.
Внутренние объекты
SegmentTree Массив, хранящий в себе дерево отрезков.
base_capacity Переменная, хранящая округлённую к ближайшей большей степени двойки размерность базы дерева отрезков.
g Указатель на функцию, которая представляет из себя ассоциативную бинарную операцию. Формально определяется как функция/операция.
neutral Нейтральный элемент относительно бинарной операции g.
Методы класса
construct

Аргументы:

  1. Адрес начала полуинтервала [latex]a[/latex];
  2. Адрес конца полуинтервала [latex]b[/latex];
  3. Ассоциативная бинарная операция f;
  4. Нейтральный элемент относительно f.

Генерирует базу на основе полуинтервала [latex]\left[a; b\right)[/latex], копируя его элементы внутрь дерева, и строит на основе этой базы дерево отрезков.
Вычислительная сложность: [latex]O\left(n\right)[/latex].

read_and_construct Аргументы:

  1. Размер базы дерева;
  2. Функция-препроцессор;
  3. Ассоциативная бинарная операция f;
  4. Нейтральный элемент относительно f.

Генерирует базу на основе элементов, возвращаемых функцией-препроцессором, и строит на их основе дерево отрезков.
Вычислительная сложность: [latex]O\left(n\right)[/latex].

assign Аргументы:

  1. Индекс элемента;
  2. Новое значение элемента.

Заменяет значение элемента с заданным индексом на новое.
Вычислительная сложность: [latex]O\left(\log_{2}{n}\right)[/latex].

result_on_segment Аргументы:

  1. Индекс левого конца отрезка;
  2. Индекс правого конца отрезка.

Возвращает результат функции на заданном отрезке.
Вычислительная сложность: [latex]O\left(\log_{2}{n}\right)[/latex].

Инструкция по применению

Прежде всего, код универсального дерева отрезков необходимо скопировать в исходную программу.

Построение:

  • Создать тип объектов (структуру данных), который будет использоваться в дереве для вычислений; (в зависимости от задачи. Вполне может быть, что необходимый для решения задачи класс уже создан. Например — int или double.)
  • Инициализировать дерево отрезков, передав классу segments_tree в качестве параметра тип объектов, над которыми будут проводиться вычисления, и задав дереву имя. (инициализация класса segments_tree происходит аналогично инициализации класса vector)
  • Построить дерево отрезков на основе заданных элементов при помощи метода construct или read_and_construct, передав методу соответствующие параметры (упомянутые в таблице выше);

Далее для вычисления результатов на отрезках и модификаций элементов с заданным индексом использовать методы result_on_segment и assign соответственно.

Пример использования

Примечание: условие и альтернативное решение приведённой ниже задачи находится по этой ссылке.

Решение задачи №4082 на www.e-olymp.com

Так как в задаче необходимо выводить знак или произведения на заданных отрезках (либо нуль), то очевидно, что сами числа не интересуют нас. Тогда каждое из них можно представить в виде пары (zero, plus)[latex]= \left(a, b\right) \in \mathbb{B}^{2}[/latex] (где [latex]\mathbb{B}[/latex] — булево множество), где первый элемент пар [latex]a[/latex] будет характеризовать равенство числа нулю, а [latex]b[/latex] — его положительность. Назовём структуру данных пар такого типа number_sign. Функция make_number_sign будет преобразовывать числа типа short в number_sign. Затем определим для этой структуры функцию умножения prod формулой prod(number_sign a, number_sign b)[latex]=[/latex] (a.zero|b.zero, !(a.plus^b.plus));. В первой части формулы используется дизъюнкция, так как произведение нуля и произвольного числа всегда должно возвращать нуль, а во второй части — эквиваленция, так как результат произведения является отрицательным, если оба аргумента различны по знаку.

Затем, предварительно считав размер базы, конструируем дерево отрезков методом read_and_construct, передавая ему число элементов базы, анонимную функцию-препроцессор, которая считывает элементы базы из входного потока и которая преобразует их в тип данных number_sign, функцию произведения prod и её нейтральный элемент number_sign(), являющийся парой [latex]\left(0, 1\right)[/latex], который по сути представляет из себя число [latex]+1[/latex] (нейтральный элемент умножения).

Остальная часть решения требует только замены старых элементов новыми и вычислений результатов на отрезках, для чего есть готовые методы класса.

Фрагмент кода

Задача 2

Дополнить класс «дерево отрезков» из первой задачи таким образом, чтобы для базы дерева были реализованы:

  • параметры «вместимость» и «размер»;
  • функции добавления нового элемента в базу;
  • функции, возвращающие размер базы и вместимость дерева;
  • функция изменения размера базы.

Написать таблицу новых функций и параметров.

Код класса

Описание дополнительных объектов класса

Название объекта Описание
Новый внутренний объект
base_size Переменная, хранящая размерность базы дерева отрезков.
Новые методы класса
begin

Аргументы: отсутствуют.
Возвращает адрес начала базы.
Вычислительная сложность: константа.

end Аргументы: отсутствуют.
Возвращает адрес конца базы.
Вычислительная сложность: константа.
push_back Аргумент: значение нового элемента базы.
Добавляет новый элемент в конец базы.
Вычислительная сложность: если база заполнена, то [latex]O\left(n\right)[/latex], иначе — [latex]O\left(\log_{2}{n}\right)[/latex].

pop_back

Аргументы: отсутствуют.
Удаляет элемент в конце базы.
Вычислительная сложность: [latex]O\left(\log_{2}{n}\right)[/latex].

insert

Аргументы:

  1. Индекс нового элемента;
  2. Значение нового элемента.

Добавляет на заданную позицию базы новый элемент с заданным значением.
Вычислительная сложность: [latex]O\left(n\right)[/latex].

erase

Аргумент: индекс удаляемого элемента.
Удаляет из базы элемент с заданным индексом.
Вычислительная сложность: [latex]O\left(n\right)[/latex].

size

Аргументы: отсутствуют.
Возвращает размерность базы дерева.
Вычислительная сложность: константа.

capacity

Аргументы: отсутствуют.
Возвращает размерность базы дерева, округлённую к ближайшей большей степени двойки. Позволяет оценить число неиспользованных ячеек, на которые уже выделена память.
Вычислительная сложность: константа.

resize

Аргумент: новый размер базы.
Изменяет размер базы дерева, и преобразовывает незадействованные элементы в нейтральные
Вычислительная сложность: [latex]O\left(n\right)[/latex], если новый размер базы превысил вместимость дерева или является меньше, чем старый, и константа в противном случае.

Задача 3: множественные модификации

Обобщённая формулировка задач этого типа несколько отличается от предыдущей:
«Пусть даны моноид [latex]\left(\mathbb{G}, \circ\right)[/latex], последовательность (массив) [latex]A[/latex] элементов из [latex]\mathbb{G}[/latex] длины [latex]n[/latex], и определена некоторая функция [latex]f: \mathbb{M} \to \mathbb{G}[/latex], где [latex]\mathbb{M}[/latex] — множество всех параметров для модификации элементов.
Для [latex]0 \le i \le j \le n-1[/latex], [latex]i, j \in \mathbb{N} \cup \{ 0 \}[/latex], даётся [latex]m[/latex] ([latex]m \in \mathbb{N}[/latex]) запросов двух типов:
1) вычислить значение выражения [latex]x_{i} \circ x_{i+1} \circ \ldots \circ x_{j-1} \circ x_{j}[/latex] с заданными [latex]i[/latex], [latex]j[/latex] и вывести его;
2) заменить значения элементов [latex]x_{k}[/latex] на [latex]f \left( y \right)[/latex], [latex]k = \overline{i, j}[/latex], [latex]y \in \mathbb{M}[/latex] (проще говоря, модифицировать отрезок [latex]\left[i, j \right][/latex] функцией [latex]f\left(y\right)[/latex]).

Как правило, в этих задачах функция [latex]f[/latex] имеет определённую закономерность относительно элементов моноида (и это естественно, так как хаотическая модификация не поддаётся никакой оценке, и единственный выход в случае хаотических множественных модификаций — напрямую модифицировать элементы дерева, что имеет асимптотику [latex]O \left( n \right)[/latex] в лучшем случае). Основная идея — использовать эту закономерность, чтобы модифицировать не весь отрезок, а только вершину в дереве, отвечающую за него, что улучшает сложность модификации отрезка до [latex]O \left( \log_{2}{n} \right)[/latex], а в случае запросов, которые затрагивают дочерние вершины, «протолкнуть» эту модификацию в них.

ПРИМЕЧАНИЕ: данная часть статьи будет существенно доработана в ближайшее время, а пока доступен код универсального класса «дерево отрезков» для задач с множественной модификацией.

Код класса

Ссылки

Просто RSQ

Задача RSQ (Range Sum Query). Вам дан массив, необходимо отвечать на запросы получения суммы на отрезке и изменение одного элемента массива.

Ссылка на задачу на codeforces.com.

Имя входного файла: rsq.in
Имя выходного файла: rsq.out
Ограничение по памяти: 2 секунды
Ограничение по времени: 256 мегабайт

Формат входного файла

Входной файл в первой строке содержит два числа [latex]n[/latex] [latex]\left(1 \le n \le 10^{5} \right)[/latex] — размер массива и [latex]m[/latex] [latex]\left(1 \le m \le 10^{5} \right)[/latex] — количество запросов. Во второй строке задано начальное состояние массива [latex]a_{1}[/latex], [latex]a_{2}[/latex], [latex]\ldots[/latex], [latex]a_{n}[/latex] [latex]\left( -10^{5} \le a_{i} \le 10^{5} \right)[/latex].

Далее идёт [latex]m[/latex] строк с запросами вида [latex]t[/latex] [latex]x[/latex] [latex]y[/latex] [latex]\left( 0 \le t \le 1 \right)[/latex]. Если [latex]t = 0[/latex], тогда на запрос нужно вывести сумму элементов массива с индексами от [latex]x[/latex] до [latex]y[/latex] (в данном случае [latex]1 \le x \le y \le n[/latex]). Если [latex]t = 1[/latex], тогда надо присвоить элементу массива с индексом [latex]x[/latex] значение [latex]y[/latex] (в этом случае [latex]1 \le x \le n[/latex], [latex]-10^{5} \le y \le 10^{5}[/latex]).

Формат выходного файла

На каждый запрос суммы отрезка выведите одно число в новой строке — запрашиваемая сумма.

Примеры

rsq.in rsq.out
5 3
1 2 3 4 5
0 1 5
1 1 -14
0 1 5
15
0
8 2
7 3 -10 4 1 2 5 6
0 2 4
0 5 7
-3
8

Код программы

Решение задачи

Основная идея приведённого выше решения этой задачи заключается в оптимизации обработки запросов суммы построением дерева отрезков.
Сохраним сумму всех элементов массива в переменной sum. Теперь, если нам дан запрос суммы на отрезке [latex]\left[ x; y \right][/latex], то если [latex]y — x > \frac{n}{2}[/latex] (то есть если данный отрезок содержит больше элементов, чем половина всего отрезка) то считаем сумму элементов на отрезке [latex]\left[ 1; x-1 \right] \cup \left[ y+1; n \right] = \left[ 1; n \right] \setminus \left[ x; y \right][/latex] и отнимаем от суммы всех элементов, иначе (если [latex]y — x \le \frac{n}{2}[/latex], то) просто считаем сумму элементов на отрезке [latex]\left[ x; y \right][/latex]. Если же поступает запрос на замену значения элемента, то вычитаем из sum старое значение и прибавляем новое.

Таким образом, максимальная сложность запросов суммы (при простом подходе к задаче) уменьшается вдвое.

Ссылки

e-olymp 4482. В стране невыученных уроков 2

Алина Гончарова
Алина Гончарова

Latest posts by Алина Гончарова (see all)

Задача

Теперь у Вити есть программа, которая помогает ему быстро находить НОД многих чисел. Поэтому стражи решили изменить правила: теперь Витя должен найти наибольший общий делитель (НОД) чисел на промежутке [l; r], а стражи – наименьшее общее кратное (НОК), у кого получится число меньше, тот и выиграет.

Входные данные

Первая строка содержит количество элементов в массивеn (1n106). Во второй строке находится n чисел – элементы ai (1ai109) массива. В третьей строке находится количество запросовm (1m 105). Далее в m строках находится по три числа q, l, r (1lrn). Если q = 1, требуется определить победителя для промежутка [l; r], если q = 2, то нужно заменить элемент в позиции l на число r.

Выходные данные

Для каждого запроса с номером 1 в отдельной строке выведите строку «wins«, если Витя выиграл, строку «loser«, если он проиграл и «draw«, если была ничья.

Решение

В данной задаче нам нужно реализовать дерево отрезков, но поменять функцию которую определяет значение в узлах. Прочитав условие можно понять, что ответ «loser» мы не выведем никогда, так как НОД не может быть больше НОК. Тогда остается определить когда выводить «wins» или «draw». НОД и НОК некоторого количества чисел равны тогда и только тогда, когда все числы для которых мы считаем НОД и НОК равны между собой. Поэтому ассоциативной функцией для построения дерева выберем функцию равенства, если числа равны возвращаем само число, иначе 0. Тогда для ответа на вопрос задачи просто следует узнать что находится в соответсвующем узле.
Если это 0, то НОК больше НОД, иначе они равны и мы выведем «draw».

Код

Тесты

Входные данные Выходные данные
5
2 4 6 10 8
6
1 1 5
1 2 3
2 5 15
2 3 10
1 3 5
1 1 1
wins
wins
wins
draw
5
7 7 7 7 7
4
1 1 5
2 2 1
1 1 5
1 3 5
draw
wins
draw

Задача взята отсюда.

Решенная задача на e-olymp.

Код программы.