Школьная индивидуальная олимпиада #1 - Codeforces Beta Round #38. (Разбор задачи G) <h1>Задача G. "Очередь"</h1>Данная задача имеет несколько возможных решений, но я расскажу 2 возможных подхода:<br><br><h2>1. Декартово дерево (дуча, treap или дерамида)</h2>Будем считать, что читатели знакомы с этой структурой (если это не так, то советую почитать <a href="http://e-maxx.ru/algo/treap">тут</a>). Самое простой по логике подход использует неявное декартово дерево, и этот алгоритм действует так: будем добавлять людей по очереди, в порядке их прихода. В вершине дерева, кроме служебной информации, будем поддерживать число $maxValue$, равное максимальному значению из чисел $a_i$ в этом дереве.<br><br>Бинарным поиском переберем возможную позицию нового человека, пусть он имеет номер $k$, $pos$ от $0$ до $c_k$ (для удобства нумерацию введем с конца очереди). Человек достигнет этой позиции тогда и только тогда, когда среди чисел $a_i$, $0 \le i < pos$ не существует ни одного, большего числа $a_k$. Это можно проверить, отщепив от декартова дерева поддерево размера $pos$, и пр...
Full text and comments »
