|
|
| Строка 1: |
Строка 1: |
| − | {| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
| |
| − | |+
| |
| − | |-align="center"
| |
| − | |'''НЕТ ВОЙНЕ'''
| |
| − | |-style="font-size: 16px;"
| |
| − | |
| |
| − | 24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
| |
| − |
| |
| − | Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
| |
| − |
| |
| − | Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
| |
| − |
| |
| − | Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
| |
| − |
| |
| − | ''Антивоенный комитет России''
| |
| − | |-style="font-size: 16px;"
| |
| − | |Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
| |
| − | |-style="font-size: 16px;"
| |
| − | |[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
| |
| − | |}
| |
| − |
| |
| | {{Шаблон:Задача | | {{Шаблон:Задача |
| | |definition =Дан массив <tex>A[1..N]</tex>. Поступают запросы вида <tex>(i, j)</tex>, на каждый запрос требуется найти минимум в массиве <tex>A</tex>, начиная с позиции <tex>i</tex> и заканчивая позицией <tex>j</tex>. | | |definition =Дан массив <tex>A[1..N]</tex>. Поступают запросы вида <tex>(i, j)</tex>, на каждый запрос требуется найти минимум в массиве <tex>A</tex>, начиная с позиции <tex>i</tex> и заканчивая позицией <tex>j</tex>. |
Текущая версия на 19:36, 4 сентября 2022
| Задача: |
| Дан массив [math]A[1..N][/math]. Поступают запросы вида [math](i, j)[/math], на каждый запрос требуется найти минимум в массиве [math]A[/math], начиная с позиции [math]i[/math] и заканчивая позицией [math]j[/math]. |
Алгоритм
Описание
Пример декартового дерева
Будем решать задачу RMQ, уже умея решать задачу LCA. Для хранения решения задачи о LCA будем использовать декартово дерево по неявному ключу. Тогда минимум на отрезке от [math] i [/math] до [math] j [/math] массива [math] A [/math] будет равен наименьшему общему предку [math]i[/math]-того и [math]j[/math]-того элементов из декартова дерева, построенного на массиве [math] A [/math].
Декартово дерево по неявному ключу на массиве [math]A[1..N][/math] — это бинарное дерево, допускающее следующее рекурсивное построение:
- Корнем дерева является элемент массива, имеющий минимальное значение [math]A[/math], скажем [math]A[i][/math]. Если минимальных элементов несколько, можно взять любой.
- Левым поддеревом является декартово дерево на массиве [math]A[1..i-1][/math].
- Правым поддеревом является декартово дерево на массиве [math]A[i+1..N][/math].
Здесь и далее [math]A[i][/math] будет также использоваться для обозначения соответствующей вершины дерева.
Построим декартово дерево на массиве [math]A[/math]. Тогда [math]RMQ(i, j)[/math] = [math]LCA(A[i], A[j])[/math].
Корректность
| Теорема: |
[math]RMQ(i, j)[/math] = [math]LCA(A[i], A[j])[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Положим [math]w = LCA(A[i], A[j])[/math].
Заметим, что [math]A[i][/math] и [math]A[j][/math] не принадлежат одновременно либо правому, либо левому поддереву [math]w[/math], потому как тогда бы соответствующий сын находился на большей глубине, чем [math]w[/math], и также являлся предком как [math]A[i][/math], так и [math]A[j][/math], что противоречит определению [math]LCA[/math]. Из этого замечания следует, что [math]w[/math] лежит между [math]A[i][/math] и [math]A[j][/math] и, следовательно, принадлежит отрезку [math]A[i..j][/math].
По построению мы также знаем, что:
- Любая вершина дерева имеет свое значение меньшим либо равным значению её детей.
- Поддерево с корнем в [math]w[/math] содержит в себе подмассив [math]A[i..j][/math].
Суммируя, получаем, что [math]w[/math] имеет минимальное значение на отрезке, покрывающем [math]A[i..j][/math], и принадлежит отрезку [math]A[i..j][/math], отсюда [math]RMQ(i, j) = w[/math]. |
| [math]\triangleleft[/math] |
Сложность
Существует алгоритм, который строит декартово дерево за [math]O(n)[/math]. Используя алгоритм построения LCA, получаем:
препроцессинг для [math]LCA[/math] — [math]O(n)[/math] и ответ на запрос — [math]O(1)[/math].
Нам нужно единожды построить декартово дерево за [math]O(n)[/math], единожды провести препроцессинг за [math]O(n)[/math] и отвечать на запросы за [math]O(1)[/math].
В итоге получили [math]RMQ[/math] с построением за [math]O(n)[/math] и ответом на запрос за [math]O(1)[/math].
См.также
