https://acm.khpnets.info/w39/index.php?action=history&feed=atom&title=Codeforces_100971.H 2026-06-02T22:10:21Z История изменений этой страницы в вики MediaWiki 1.39.3 https://acm.khpnets.info/w39/index.php?title=Codeforces_100971.H&diff=2032&oldid=prev 2016-06-08T20:12:00Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="ru"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Предыдущая версия</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Версия от 20:12, 8 июня 2016</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l9">Строка 9:</td> <td colspan="2" class="diff-lineno">Строка 9:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Будем перебирать количество друзей k, приходящих на вечеринку (от 1 до n). Для фиксированного количества друзей сначала обработаем все события, связанные с количеством k, а затем требуется вывести длину минимального префикса массива goToParty[], сумма на котором равна k.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Будем перебирать количество друзей k, приходящих на вечеринку (от 1 до n). Для фиксированного количества друзей сначала обработаем все события, связанные с количеством k, а затем требуется вывести длину минимального префикса массива goToParty[], сумма на котором равна k.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Для быстрого подсчёта суммы на префиксе <del style="font-weight: bold; text-decoration: none;">можно </del>использовать дерево Фенвика или дерево отрезков<del style="font-weight: bold; text-decoration: none;">. Подобрать </del>минимальный нужный префикс <del style="font-weight: bold; text-decoration: none;">можно </del>бинарным поиском.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Для быстрого подсчёта суммы на префиксе <ins style="font-weight: bold; text-decoration: none;">есть два способа:</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* Можно </ins>использовать дерево Фенвика или дерево отрезков <ins style="font-weight: bold; text-decoration: none;">с запросом суммы на отрезке и подбирать </ins>минимальный нужный префикс бинарным поиском<ins style="font-weight: bold; text-decoration: none;">. Сложность O(log^2(n)).</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* Можно использовать спуск по дереву отрезков на сумму, ища индекс k-й единицы. Сложность O(logn)</ins>.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category: Сборник задач: Codeforces]]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category: Сборник задач: Codeforces]]</div></td></tr> </table>

Ctrlalt https://acm.khpnets.info/w39/index.php?title=Codeforces_100971.H&diff=2031&oldid=prev 2016-06-08T17:05:46Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="ru"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Предыдущая версия</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Версия от 17:05, 8 июня 2016</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">Строка 1:</td> <td colspan="2" class="diff-lineno">Строка 1:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Ссылка на задачу ==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Ссылка на задачу ==</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* [http://codeforces.com/gym/100971/problem/H Codeforces #100971.H &amp;mdash; <del style="font-weight: bold; text-decoration: none;">Остров сокровищ</del>]</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* [http://codeforces.com/gym/100971/problem/H Codeforces #100971.H &amp;mdash; <ins style="font-weight: bold; text-decoration: none;">Тусовка у Павла</ins>]</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Комментарии ==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Комментарии ==</div></td></tr> </table>

Ctrlalt https://acm.khpnets.info/w39/index.php?title=Codeforces_100971.H&diff=2030&oldid=prev 2016-06-08T17:05:20Z

<p>Новая страница: «== Ссылка на задачу == * [http://codeforces.com/gym/100971/problem/H Codeforces #100971.H — Остров сокровищ] == Коммент…»</p> <p><b>Новая страница</b></p><div>== Ссылка на задачу ==<br /> * [http://codeforces.com/gym/100971/problem/H Codeforces #100971.H &amp;mdash; Остров сокровищ]<br /> <br /> == Комментарии ==<br /> Заведём массив goingToParty[], в котором будем отмечать, собирается ли прийти на вечеринку каждый из друзей.<br /> <br /> Каждая пара (a&lt;sub&gt;i&lt;/sub&gt;, b&lt;sub&gt;i&lt;/sub&gt;) даёт 2 события: когда на вечеринку идут a&lt;sub&gt;i&lt;/sub&gt; человек, i-й друг также приходит (goingToParty[i] = 1), а когда на вечеринку идут (b&lt;sub&gt;i&lt;/sub&gt; + 1) человек, i-й друг уже не приходит (goingToParty[i] = 0).<br /> <br /> Будем перебирать количество друзей k, приходящих на вечеринку (от 1 до n). Для фиксированного количества друзей сначала обработаем все события, связанные с количеством k, а затем требуется вывести длину минимального префикса массива goToParty[], сумма на котором равна k.<br /> <br /> Для быстрого подсчёта суммы на префиксе можно использовать дерево Фенвика или дерево отрезков. Подобрать минимальный нужный префикс можно бинарным поиском.<br /> <br /> [[Category: Сборник задач: Codeforces]]<br /> [[Category: Задачи: Сканирующая прямая]]<br /> [[Category: Задачи: Дерево отрезков]]<br /> [[Category: Задачи: Дерево Фенвика]]<br /> [[Category: Задачи: Бинарный поиск]]</div>

Ctrlalt