В этом году проходил BSUIR Open XIV, мне было очень приятно съездить в Минск и на само соревнование. Но еще больше мне понравилась задачу, которую я туда предложил. В целом я не видел эту идею раньше, но она кажется достаточно простой, чтобы появиться раньше на каких-нибудь соревнованиях. Так что если вы знаете, где раньше встречалась это идея, то поделитесь, пожалуйста.

Задача. (*BSUIR OPEN XIV*) Дано клеточное поле $$$100 \times 100$$$, в котором между некоторыми клетками проведены стены, также стены проведены по границе поля. Луч запускается из центра клетки $$$(r,c)$$$ в направлении $$$(x,y)$$$. Требуется определить, в какой клетке он окажется, пройдя расстояние $$$\sqrt{x^2+y^2}$$$, если луч отражается от стен.

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

Взглянем на вектор $$$(x,y)$$$ и посмотрим, в каком порядке он пересекает вертикальные и горизонтальные линии сетки. В точке $$$(0,0)$$$ пересечение с линиями сетки учитывать не будем, но будем учитывать пересечения в точке $$$(x,y)$$$, причем по формальным причинам мы будем считать, что сначала происходит пересечение с вертикальной прямой.

Последовательность пересечений можно записать в виде строки:

• $$$R$$$ обозначает пересечение вертикальной линии сетки (перемещение на клетку вправо),
• $$$U$$$ обозначает пересечение горизонтальной линии сетки.

Тогда каждому вектору $$$(x,y)$$$ можно сопоставить строку $$$s(x, y)$$$, содержащую последовательность этих пересечений. Например,

Предположим, что $$$x \ge y$$$. Это означает, что вектор «пологий», и перед каждым пересечением горизонтальной линии происходит пересечение вертикальной. А именно, перед $$$k$$$-м символом U стоит

подряд идущих символов R.

Таким образом, перед каждым символом U стоит блок, состоящий как минимум из $$$\left\lfloor x/y \right\rfloor$$$ символов R; эти блоки вместе с символами U можно сжать в один символ. Например,

Таким образом, можно предположить, что если $$$s(x, y, R, U)$$$ — это строка $$$s(x,y)$$$, где на месте символов R и U стоят строки $$$R$$$ и $$$U$$$, то верно равенство:

Ясно, что это правда. Например, в случае $$$x \ge y$$$ достаточно убедиться в том, что перед $$$k$$$-м символом $$$U$$$ после подстановки сохраняется количество подряд идущих букв R:

Таким образом, строку $$$s(x,y)$$$ можно вычислять с помощью алгоритма Евклида. Разумеется, в общем случае нам нужна не строка, а какая-то более полезная информация. Символы R и U могут принадлежать произвольному моноиду, для которого можно эффективно вычислять следующие операции:

• произведение элементов;
• возведение элемента в степень.

Например, в качестве моноида могут выступать перестановки, матрицы или любые другие объекты, которые можно поддерживать в дереве отрезков. В частности, в подстроке $$$s(x,y)$$$ можно поддерживать количество подпоследовательностей UR, что соответствует вычислению значения floor_sum (только в таком случае надо аккуратно разобраться с приоритетами символов R и U).

Обобщённо алгоритм трекинга вектора может быть реализован следующим образом:

template <typename M>
M GridEuclide(u64 x, u64 y, M R, M U) {
    while (x && y) {
        if (x >= y) {
            const u64 k = x / y;
            x -= y * k;
            U = R.Pow(k) * U;
        } else {
            const u64 k = (y - 1) / x;
            y -= x * k;
            R = U.Pow(k) * R;
        }
    }
    return !x ? U.Pow(y) : R.Pow(x);
}

Другие обобщения

В ходе алгоритма можно строить не композицию моноидов $$$R$$$ и $$$U$$$, а последовательность неполных частных вместе со всеми промежуточными вычислениями. Например, при входных данных $$$(x,y)$$$ таблица вычислений будет выглядеть следующим образом. Напомним, что

Работая со всеми промежуточными вычислениями, можно дополнительно обрабатывать следующие сценарии:

• композицию моноидов $$$R$$$ и $$$U$$$ на любом подотрезке $$$(l,r)$$$ строки $$$s(x,y)$$$.

Так, если запускать вектор не из точки $$$(0,0)$$$, а из произвольной точки $$$(\alpha, \beta)$$$, то может получиться строка $$$s(x,y,\alpha,\beta)$$$, отличная от $$$s(x,y)$$$. Но также ясно, что строка $$$s(x,y,\alpha,\beta)$$$ получается циклическим сдвигом строки $$$s(x,y)$$$.

Чтобы понять, что именно это будет за циклический сдвиг, вспомним, что строку $$$s$$$ можно представить в виде объединения блоков вида R...RU, где количество букв R перед $$$k$$$-й буквой U вычисляется по формуле:

Таким образом, если вектор запускается из произвольной точки $$$(\alpha/y, 0)$$$, то длина $$$k$$$-го блока будет вычисляться по похожей формуле:

В случае взаимной простоты $$$x$$$ и $$$y$$$ можно сделать замену

И тогда число $$$k_0$$$ и будет искомым циклическим сдвигом.

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

можно вычислить за время

в общем случае, что достаточно приятно.

Привет всем участникам платформы Codeforces! В эту субботу состоится студенческий финал BSUIR Open XIII, а вместе с ним пройдут раунды Codeforces Round 1021 (Div. 1) и Codeforces Round 1021 (Div. 2) в 26.04.2025 11:35 (Московское время) по задачам этого тура. Обратите внимание на то, что раунд стартует в необычное время.

В этом году задачи для раунда и олимпиады готовили teraqqq, FairyWinx, Kirill22 и wilcot; в каждом раунде будет 6 задач, и у вас будет 3 часа на их решение. Отметим, что wilcot уже не первый год составляет задачи для BSUIR Open и привлекает новых авторов к участию в этом событии. Мы считаем, что именно благодаря этому в этом году получился разносторонний и интересный студенческий финал из части которого получилось составить раунд на codeforces.

Выражаем особую благодарность MikeMirzayanov, geranazavr555 и KAN за замечательные системы Polygon и Codeforces! Также выражаем благодарность:

• Artyom123 за координирование раунда и привлечение тестеров;
• arvindf232, A_G, N_z__, jtrh, __jk__, reirugan и larush за тестирование раунда;
• Golovanov399, SomethingNew, allvik66, golikovnik и OG_Matveychick1 за тестирование задач олимпиады;
• i_love_gold_and_nt, Gornak40 за помощь составлением условий.

Отдельно хотим сказать спасибо людям, благодаря которым состоялся BSUIR Open XIII:

• Великовичу Владимиру, Швед Елизавете, Внук Ольге, Юрченко Ольге, Гороху Андрею, Макаревич Дарье и Севрюкову Степану за организацию чемпионата;
• Удовину wilcot Ивану, Марковцу Роману, Байтасову Ринату, Ромашевскому Герману, Бутоме Виталию, Любашенко Андрею и Ситникову Алексею за подготовку задач полуфинала;
• Ефимчику Александру и Адарову Дмитрию за техническое сопровождение чемпионата;

Чемпионат BSUIR Open уже который год проход в стенах БГУИР. Каждый раз организаторы мероприятия вносят что-то новое, уникальное и незабываемое. Благодаря ним BSUIR Open уже который год радует участников дружеской атмосферой, интересными задачами и приятными подарками!

UPD. Разбалловка задач:

Div 2: $$$500 + 1250 + 1500 + 2250 + 2750 + 3250$$$

Div 1: $$$500 + 1000 + 1500 + 2000 + 3000 + 3500$$$

UPD2: Разбор

Приветствуем вас, фанаты олимпиадного программирования и любители написать раунды на Codeforces! Мы рады пригласить вас поучаствовать в Hello 2025, он состоится в 04.01.2025 17:35 (Московское время).

Мы, teraqqq, dope и induk_v_tsiane, подготовили для вас 8 задач, и у вас будет 2 часа 30 минут на их решение. Одна из задач разделена на 2 подзадачи. Раунд будет рейтинговым для всех участников.

Выражаем огромную благодарность MikeMirzayanov, geranazavr555 и KAN за замечательные системы Polygon и Codeforces! Также выражаем благодарность:

• FairyWinx за координаторство этого раунда, поиск тестеров, моральную и техническую поддержку.
• turmax, LeoPro, Kapt, sevlll777, Pechalka, Adam_GS, evjeny_23, Iura_Shch, Noobish_Monk, Chalishkan, BottleOfJuice, v0s7er, Error_Yuan, zwezdinv, RP-1, mz1, RomkaRS, epcgmein, golikovnik, KiruxaLight за тестирование раунда.
• Анне @yaognennaya Зайцевой за моральную поддержку наших проектов.

Разбалловка: 500 — 1000 — 1500 — 2250 — (1000+2000) — 3500 — 3750 — 4500

UPD. Разбор доступен по ссылке

Отметим, что этот раунд разработан при поддержке кружка Т-Поколения "Алгоритмы и структуры данных".

Т-Поколение "Алгоритмы и структуры данных" — это бесплатный кружок по подготовке к олимпиадам по информатике и спортивному программированию. Кружок проходит как онлайн, так и очно в Москве, Санкт-Петербурге, Казани, Екатеринбурге, Ижевске, Нижнем Новгороде, Новосибирске, Перми, Уфе и Челябинске. Учебная программа делится на 4 параллели по уровню обучающихся:

• Параллель X предназначена для опытных олимпиадников, в ней преподают: Бабин teraqqq Александр, Нагибин Pechalka Всеволод, Белый antonis.white Антон и Бугрышев vdv09 Михаил в Москве и онлайн; Иванов orz Михаил и Леонид LeoPro Данилевич в Санкт-Петербурге.

• Параллель B предназначена для тех, кто уверенно проходит на региональный этап ВсОШ, хочет научиться проходить на заключительный этап и брать там диплом призера. В этой параллели преподают: Горбунов Gornak40 Александр, Паншин doing Игорь, Зайцев MadProgrammer Михаил, Белоусько Alcabel Константин в Москве и онлайн; Григорьев sava-cska Савелий в Санкт-Петербурге.

• Параллель B' предназначена для тех, кто на базовом уровне владеет C++, участвовал в муниципальных этапах ВсОШ и хочет подготовиться к региональному этапу ВсОШ и перечневым олимпиадам. В этой параллели преподают: Подворный Иван, Чистяков alexchist Александр, Зорин zorianka Кирилл, Чуканов Тимофей в Москве и онлайн; Дзестелов Хетаг в Санкт-Петербурге; Валеев OrleanMagic Ильнур и Иликаев Ferume Артем в Казани.

• Параллель C предназначена для тех, кто на базовом уровне владеет Python или C++ и только начал свой путь в олимпиадном программировании. В этой параллели преподают: Ремпель DimaTomsk Дмитрий, Кривощеков robivirt Виктор, Антонова Анна, Никитин BPCorp Артем в Москве и онлайн; Хорохорин Андрей, Добрынин DIvanCode Иван в Санкт-Петербурге; Кориненко m0t9_ Матвей в Казани; Парамонова Екатерина в Екатеринбурге; Лукичев Александр в Ижевске; Шмелев ashmelev Алексей, Алясева Diall_ Диана, Шаяхметов l-_-l Ислам в Нижнем Новгороде; Львов APLion Антон в Новосибирске; Юрчатов SonOfShushpanchick Арсений в Перми; Нигматуллин Enigmaster Вадим в Уфе; Голодов golodov.valentin Валентин и Карпович 74TrAkToR Евгений в Челябинске! (Да, нас много)

Кружок открывает донабор, который проходит с 6 января по 13 января, регистрация уже доступна по ссылке! По всем вопросам можете обращаться @yaognennaya в телеграмме.

Помимо проведения кружков в течение учебного года мы проводим дополнительные, открытые для всех, мероприятия: TOI (авторские тренировочные туры для подготовки к региональному и муниципальному этапу ВсОШ) и Сборы к региональному этапу. Если вы хотите видеть анонсы этих и других мероприятий Т-Образования, то можете подписаться на соответствующий канал.

Призеры всероссийской олимпиады школьников по информатике за 11 класс, успешно закончившие кружок, получат на первом году обучения в вузе стипендию от Т-Банка.

Мы рады обучать всех. Если вы не проживаете в городах очного присутствия Т-Поколения или находитесь не в России, то вы все равно сможете заниматься в кружке, но в онлайн-формате. Обратите внимание, что занятия ведутся на русском языке.

UPDATE

Поздравляем победителей:

1. jiangly

2. ksun48

3. ugly2333

4. Flamire

5. Ormlis

6. hos.lyric

7. ecnerwala

8. noimi

9. maspy

10. arvindf232

Всем привет! Хочу рассказать о достаточно простом приеме (не знаю как называется) для оптимизации динамики. Очень часто бывает так, что при пересчете нам надо искать минимум в какой-нибудь уже посчитанной таблице, но при этом игнорируя некоторое конечное количество строк и столбцов; как оптимизировать такое и подобное, описано в блоге.

Постановка задачи

Итак, у нас есть таблица, предположим, что большая — $$$N \times N$$$, и мы хотим сделать какое-то большое количество запросов вида «Найди максимальное значение в таблице, которое не лежит в столбцах из множества $$$C$$$ и строках из множества $$$R$$$», при этом для каждого запроса гарантируется, что $$$max ( |C|, |R| ) \leq K$$$, где $$$K$$$ -- какая-то очень маленькая константа. Эту задачу мы бы могли решать, например, с помощью двумерного ДО -- но это работает долго и занимает гораздо больше памяти.

Решается задача просто, давайте для начала, найдем $$$x_1$$$ — глобальный максимум в таблице и запомним его позицию $$$(i_1, j_1)$$$. Далее, при дальнейших запросах, возможен вариант, что либо $$$i_1 \in C$$$, либо $$$j_1 \in R$$$, поэтому давайте запустим два рекурсивных вызова, с поиском максимума в таблице, в одном из них запретив строку $$$i_1$$$, а в другом -- столбец $$$j_1$$$. Таким образом каждая рекурсивная функция считает максимум, в случае, если мы запрещаем столбцы $$$C'$$$ и строки $$$R'$$$. Заметим, что при $$$C' \gt k$$$ и $$$R' \gt k$$$ значения нам считать не надо, так что можно смело обрывать рекурсию.

struct Candidate {
    int value;
    int x, y;

    bool operator < (const Candidate& c) const {
        return value < c.value;
    }
};

Candidate get_neutral_candidate() {
    return Candidate { numeric_limits<int>::min(), -1, -1 };
}

struct CandidateSet {
    vector<Candidate> v;
    vector<pair<int, int>> go;

    // data -- исходный массив
    // kx -- максимальное количество запретов по строкам
    // ky -- максимальное количество запретов по столбцам
    CandidateSet(const vector<vector<int>>& data, int kx, int ky) {
        set<int> x, y;
        build(data, x, y, kx, ky);
    }

    int build(const vector<vector<int>>& data, set<int>& x, set<int>& y, int kx, int ky) {
        int res = v.size();

        v.push_back(get_neutral_candidate());
        go.emplace_back(-1, -1);

        for (int i = 0; i < data.size(); ++i) {
            if (x.count(i)) continue;
            for (int j = 0; j < data[i].size(); ++j) {
                if (y.count(j)) continue;
                v.back() = max(v.back(), Candidate { data[i][j], i, j });
            }
        }

        if (v[res].x == -1) {
            v.pop_back();
            go.pop_back();
            return -1;
        }

        if (kx != 0) {
            x.insert(v[res].x);
            go[res].first = build(data, x, y, kx - 1, ky);
            x.erase(v[res].x);
        }

        if (ky != 0) {
            y.insert(v[res].y);
            go[res].second = build(data, x, y, kx, ky - 1);
            y.erase(v[res].y);
        }

        return res;
    }

    Candidate get_max(int x, int y) {
        auto ans = get_neutral_candidate();
        for (auto& s : v) if (s.x != x && s.y != y) ans = max(ans, s);
        return ans;
    }

    Candidate get_max(const set<int>& x, const set<int>& y) {
        auto ans = get_neutral_candidate();
        for (auto& s : v) if (!x.count(s.x) && !y.count(s.y)) ans = max(ans, s);
        return ans;
    }
};

Чтобы в таком случае искать максимум можно просто пройтись по кандидатам $$$O(C_{2K}^K)$$$ или используя дерево рекурсивных вызовов пройтись по нему и найти максимум за $$$O(K)$$$, во всяком случае, вы понимаете, что это работает быстро. Да, кстати, по очевидным причинам алгоритм построения этой таблицы работает за $$$O(N^2 \cdot C_{2K}^K)$$$, и алгоритм является корректным. Почему? Ну потому что если вдруг глобальный максимум не будет запрещен по обоим кандидатам, то очевидно, это будет ответ на запрос, а в ином случае, если запрещена строка, в которой он находится, то в одном из рекурсивных вызовов мы посчитали другого кандидата и так далее.

Почему это бывает полезно?

Приведу пример задачи на эту тему. У нас есть дерево размером $$$N$$$, в каждой вершине которого записана буква от $$$a$$$ до $$$z$$$, назовем строку хорошей, если ни одна его подстрока длиной больше $$$1$$$ не является палиндромом. Требуется найти максимальную подпоследовательность, какого-то простого пути в дереве, такую, что если записать символы в вершинах этой последовательности, то получится хорошая строка.

Докинем в афлавит фиктивный символ $$$\epsilon$$$. За $$$\Sigma$$$ обозначим размер алфавита, в данном случае $$$\Sigma = 26 + 1$$$. Заведем трехмерную динамику $$$dp$$$ с размерностью $$$N \times \Sigma \times \Sigma$$$, в $$$dp[v][i][j]$$$ будем хранить максимальную подпоследовательность, пути идущего сверху-вниз до вершины $$$v$$$, два последних символа которой равны $$$i$$$ и $$$j$$$, $$$i=j=\epsilon$$$ значит, что строка пустая, $$$i=\epsilon$$$ значит, что строка содержит ровно один символ. Динамика очень легко пересчитывается и это суммарно отработает за $$$O(N \cdot \Sigma ^ 2)$$$. Чтобы посчитать ответ на задачу требуется перебрать LCA двух конечных вершин пути и с помощью посчитанных значений динамики найти максимальное значение $$$dp'[u][x][y] + dp[v][z][w]$$$, где $$$dp'[u]$$$ обозначает динамику $$$dp$$$, посчитанную для путей исходящих из поддерева вершины $$$u$$$ и заканчивающих свой путь в предке $$$u$$$, при этом $$$u$$$ и $$$v$$$ -- братья и при этом $$$y \neq z$$$, $$$y \neq w$$$, $$$x \neq z$$$. При этом такой максимум уже можно найти за $$$O(N{\Sigma}^4)$$$, это медленно.. Можно постараться и найти его за $$$O(N{\Sigma}^3)$$$. Но с помощью структуры данных, описанных выше это можно сделать тривиальным образом за $$$O(N{\Sigma}^2)$$$.

Кстати, с помощью нашей структуры данных можно пойти гораздо дальше. Можно сказать, что все состояния динамики нам совершенно не нужны. Давайте вместо трехмерной динамики $$$dp$$$ построим динамику $$$dc$$$ размера $$$N$$$, основанную на CandidateSet, в котором есть не более одного запрета $$$x$$$ и не более двух запретов на $$$y$$$, для каждого состояния исходной динамики. Пересчитывать ее очень просто и приятно -- это работает за $$$O(N)$$$, единственная вещь, которую я не описал -- это объединение множества кандидатов и его обрезание, но я верю в то, что вы и сами справитесь :D. Утверждается, что глобальный максимум по $$$dp'[u][x][y] + dp[v][z][w]$$$ достигается и среди сумм $$$dc'[u][x][y] + dc[v][x][y]$$$, определенных по такому же принципу. Доказать это очень просто, пусть это останется как упражнение читателю, но с помощью этого простого трюка наше решение превращается в гордый $$$O(N)$$$ с большой константой. Ура!

Итак, многие из Вас знают, что можно легко и просто хешировать множества. Например, множество $$$s = { s_1, s_2, ..., s_n }$$$ можно захешировать числом $$$x(s_1) + x(s_2) + ... + x(s_n)$$$ или даже $$$x(s_1) \oplus ... \oplus x(s_n)$$$ (где $$$x$$$ — какая-то случайная функция). С такими хешом можно поддерживать операции добавления и удаления элемента, слияния множеств, нахождения симметричной разности множеств и так далее. Но у такого подхода есть и достаточно серьезный минус, например, имея на руках только хеш мы не можем понять, какие элементы содержит это множество.

Сегодня я хочу поведать о не очень сложной структуре данных, основанной на дереве отрезков, которая позволяет совершать различные операции с множествами, в частности, сравнивать эти множества за время O(1), надеюсь, после прочтения вы поделитесь своими идеями, как ее можно улучшить и какие еще операции с ней можно делать. :D

Итак, для начала рассмотрим следующую задачу. В первой строке даны числа $$$N,Q \leq 10^5$$$, отвечая на запросы нам требуется поддерживать $$$N$$$ множеств, пронумерованные числами от 1 до $$$N$$$. В последующих $$$Q$$$ строках указаны запросы, каждый из которых может иметь следующий вид:

• $$$1$$$ $$$i$$$ $$$x$$$ — добавить в $$$i$$$-ое множество элемент $$$1 \leq x \leq N$$$, если $$$x$$$ уже содержится в этом множестве, то ничего делать не надо

• $$$2$$$ $$$i$$$ $$$x$$$ — удалить элемент $$$1 \leq x \leq N$$$ из $$$i$$$-ого множества, аналогично, если элемента в множестве нет, то множество не изменяется

• $$$3$$$ $$$i$$$ $$$j$$$ — скопировать множество $$$j$$$ в множество с номером $$$i$$$.

Да, эту задачу можно решать теми же хешами и персистентными декартовыми деревьями, но это слишком сложно. На самом деле задача намного проще чем это кажется на первый взгляд. Давайте заведем дерево отрезков на $$$N$$$ элементов, где каждой вершине будет присвоен некоторый класс $$$h$$$, который будет обладать следующими несложными свойствами:

• $$$h_v = 0$$$ тогда и только тогда, когда нет ни одного числа, за которое ответственно поддерево вершины $$$v$$$.

• $$$h_v = 1$$$ тогда и только тогда, когда $$$v$$$ — лист, и число, соответствующее этой вершине содержится в множестве.

• в ином случае $$$h_v$$$ однозначно определяется классами левого и правого ребенка вершины $$$v$$$ и наоборот.

Понятно, что заранее мы никак не можем определить классы на все случаи жизни, так что давайте постепенно будем их добавлять по мере надобности, для этого заведем функцию vertex(i, j), которая по классам i и j будет определять класс вершины, являющейся родителем этих вершин:

int pl[C], pr[C], vc=2;
map<pair<int, int>, int> tab;
int vertex(int i, int j) {
    if (i == 0 && j == 0) return 0;
    int& x = tab[{i, j}];
    if (x == 0) {
        x = vc++;
        pl[x] = i; // классы левого и правого ребенка для любого класса заданы однозначно
        pr[x] = j;
    }
    return x;
}

Дело остается за малым, давайте напишем стандартное дерево отрезков и будет нам счастье! Но, к сожалению все не так просто, если мы будем честно поддерживать дерево отрезков то на поддержку $$$N$$$ деревьев нам понадобится $$$O(N^2)$$$ памяти, вместо этого давайте просто поддерживать класс, к которому относится корень нашего дерева отрезков, но уже, кстати, неявного, ведь по классу вершины можно однозначно восстановить классы ее сыновей. Запросы добавления и удаления ограничиваются спуском по дереву и аккуратным пересчетом классов вершин, код, поясняющий данную идею:

int add(int v, int l, int r, int x) {
    if (l + 1 == r) {
        return 1;
    } else {
        int m = (l + r) / 2;
        if (x < m) {
            return vertex(add(pl[v], l, m, x), pr[v]);
        } else {
            return vertex(pl[v], add(pr[v], m, r, x));
        }
    }
}
 
int del(int v, int l, int r, int x) {
    if (l + 1 == r) {
        return 0;
    } else {
        int m = (l + r) / 2;
        if (x < m) {
            return vertex(del(pl[v], l, m, x), pr[v]);
        } else {
            return vertex(pl[v], del(pr[v], m, r, x));
        }
    }
}

Данные функции возвращают класс полученного множества целиком, для того, чтобы сравнить два множества требуется просто сравнить их классы, которые по совместительству и являются идентификаторами наших множеств. Кстати, это весь код решения, исключая ввод и вывод данных. Функции del и add работают за $$$O({\log}^2 n)$$$ или за $$$O(\log n)$$$ если в функции vertex использовать unordered_map, так же возможны константные оптимизации.

Теперь предоставлю упражнения читателям, то есть те вещи, которые умеет делать эта структура, но на которых мне не хочется подробно останавливаться:

• Найти минимальный элемент принадлежащий ровно одному множеству из двух множеств $$$a$$$ и $$$b$$$ (просто спуск по дереву отрезков).

• Объединение двух множеств (при условии, что нет операции клонирования).

• Удаление всех элементов множества, меньших чем $$$x$$$, а так же больших чем $$$x$$$.

• Всевозможные суммы, lower_bound и почти все, что умеет обычное ДО.

К тому же, если элементы, хранимые в множестве это, например, не числа, или слишком большие числа, то использование дерева отрезков может быть невозможно, для таких целей можно аналогичным образом хешировать и декартовы деревья. Но тогда по значению ключей, хранящихся в декартовом дереве должна однозначно восстанавливаться структура дерева, добиться этого можно, если значением приоритета вершина будет какая-то функция, зависящая от ключа в вершине (можно, например, просто сохранять приоритет для ключей в unordered_map, хотя, как кажется это немного неадекватно). При совпадении ключа надо считать, что приоритет выше у той вершины, у которой больше соответствующий ключ. Тогда все операции будут выполнимы за $$$O(\log n)$$$ с использованием $$$O(n \log n)$$$ памяти.

Данное рассуждение можно распространить и для хеширования персистентных стеков (обычные стеки всегда можно заменить на персистентные без особых потерь). Тогда хеш пустого стека примем равным $$$0$$$, а хеш стека $$$S$$$ будет взаимнооднозначно определяться хешем стека $$$S$$$ без верхнего элемента и верхним элементом стека $$$S$$$. Условно говоря, это другой взгляд на хранение персистентного стека с помощью дерева.

Теперь перейдем к задачам, которые можно решить с помощью этой структуры данных или описанных выше идей.

(Задача 1). Пусть дано подвешенное дерево на $$$N \leq 10^5$$$ вершинах, где в каждой в каждой вершине $$$v$$$ написано какое-то натуральное число $$$A_v \in { 1, 2, ... , N }$$$. Рассмотрим все вертикальные пути (простой путь у которого один конец это предок другого конца) длины $$$K$$$, для каждого пути посчитаем множество чисел, записанных на вершинах этого пути. Требуется вывести количество различных множеств, которые мы можем определить.

(Задача 2). Есть страна, состоящая из $$$N \leq 10^5$$$ городов, далее с ней по очереди происходят $$$Q$$$ действий, каждое из которых относится к одному из следующих типов:

1. Добавляется ребро $$$(u, v)$$$.
2. В город $$$v$$$ приезжает ученый, который занимается наукой с порядковым номером $$$1 \leq x \leq 10^6$$$.
3. Запрос вида $$$(u, v, R)$$$, на который требуется ответить минимальным натуральным числом $$$L$$$ таким, что, область науки $$$L \leq x \leq R$$$ развита в компоненте связности вершины $$$u$$$ тогда и только тогда, когда он развита в компоненте $$$v$$$. Область науки развита в компоненте связности тогда и только тогда, когда хотя бы в одном городе из этой компоненты есть ученый, занятый этой областью.
4. По приказу государства этой страны все ученые из компоненты вершины $$$v$$$, занимающиеся науками из отрезка $$$[L,R]$$$ переезжают в компоненту $$$u$$$.

(Задача 3). Есть подвешенное дерево, на каждом ребре которого записана какая-нибудь латинская буква. Скажем, что корню соответствует пустая строка $$$s(v_0) = \epsilon$$$, а вершине $$$v$$$, из которой ведет ребро с символом $$$w$$$ в ее предка $$$p$$$, сопоставим строку $$$s(v) = w \cdot s(p)$$$. Требуется для любой пары вершин $$$(u,v)$$$ уметь лексикографически сравнивать строки $$$s(u)$$$ и $$$s(v)$$$ за время $$$O(\log N)$$$ и c предпосчетом за $$$O(N \log^2 N)$$$ без использования рандомизированных алгоритмов.

(Задача 4). Даны $$$N$$$ чисел $$$a_1, a_2, \ldots, a_N$$$ в двоичной системе счисления суммарной длиной $$$M$$$. Требуется уметь сравнивать на больше/меньше $$$(a_i \mod 2^x)$$$ с $$$(a_j \mod 2^y)$$$ за время $$$O(1)$$$ и с предпосчетом за время $$$O(M \log N)$$$.

По-хорошему, все эти идеи описывают несколько извращенную персистентность и хеширование деревьев. При достаточной степени развязности сексуальных предпочтений можно так же понять, какой смысл имеет такое хеширование при рассмотрении ориентированных графов, как таким образом можно научиться "хешировать" деки и, например, что метод построения суффиксного массива за $$$O(N \log N)$$$ тесно связан с этой идеей.

Доброго времени суток! Началось все с того, что после прочтения статьи про встречное дерево Фенвика, я начал искать в интернете его реализацию, но (спойлер) так и не нашел. Безусловно, тема не нова, но, к сожалению, статью, описывающую эту структуру данных с приведенными примерами реализации, я так и не нашел. Перед прочтением данного поста советую ознакомиться с указанной статьей, т.к. на нее будут опираться все дальнейшие рассуждения.

Встречное дерево Фенвика

Для начала, вспомним определение: Встречное дерево Фенвика (англ. counter tree Fenwick) — дерево Фенвика, в котором над каждым столбцом идет столбец такой же высоты, вычисляемый по формуле $$$f_{rev}[i]=\sum\limits_{j=i+1}^{i+2^{h(i)}}a[j]$$$. Сразу сделаю уточнение, что под прямым деревом Фенвика подразумевается массив, посчитанный формуле: $$$f_{for}[i]=\sum\limits_{j=i-2^{h(i)}+1}^i a[j]$$$. Для пущей понятности, прикреплю картинку.

Зная только то, что встречное дерево Фенвика симметрично прямому, мы можем написать код для построения встречного и прямого деревьев Фенвика, где F — функция, значение которой мы хотим считать на отрезках:

void bit_build(int n, int src[]) {
	int m = 1; while(m < n) m *= 2; m -= 2;
	for(int i = 0; i < n; ++i) {
		a[i] = src[i]; // прямое дерево Фенвика
		b[i] = i+1 < n ? src[i+1] : NEUTRAL; // встречное дерево Фенвика
	}
	for(int i = 0, j; i < n; ++i) {
		const int j = i|i+1;
		if(j < n) a[j] = F(a[i], a[j]);
	}
	for(int i = m-n+2; i < m; ++i) {
		const int j = i|i+1;
		const int u = m-i, v = m-j;
		if(j < m) b[v] = F(b[v], b[u]);
	}
}

При $$$n=2^k$$$ видно, что отрезки, покрываемые прямым и обратным деревом Фенвика идентичны дереву отрезков длины n. Из этого видно, что любой отрезок делится на два других отрезка так, что один из них полностью покрывается встречным деревом Фенвика, а другой — прямым.

Остается только сопоставить получившееся дерево Фенвика и ДО. Представлю иллюстрацию для случая n=8.

Отсюда становятся очевидными три важных факта:

1. Каждая вершина ДО (кроме листьев) составленная из элементов дерева Фенвика имеет две дочерние вершины, имеющие одинаковые индексы, но одно из них лежит в прямом дереве Фенвике, а другое во встречном.

2. В двоичной системы счисления номера листья оканчиваются на "0", вершины лежащие на втором снизу уровне обладают суффиксом "01", на третьем — "011", четвертом — "0111" и т.д.

3. Номера вершин ДО, лежащих на одном уровне, строго возрастают в порядке слева-направо.

Рассматривая номера вершин на пути от листа $$$v$$$ легко проверить, что все вершины при их записи в двоичной системе счисления будут иметь префикс такой же, как у $$$v$$$, но суффикс будет другим, в зависимости от того, на каком уровне лежит вершина. Массив же, которому принадлежит вершина будем определять непосредственно смотря на значение очередного бита в номере листа. Пример пути от листа до верхней вершины дерева отрезков для позиции номер 20 в массиве.

Дальше, я надеюсь, идея обновления значения элемента в массиве становится понятной — просто обновляем значение листа, отвечающего за значение нужного элемента массива и идем вверх, пересчитывая значения всех рассматриваемых вершин. Поиск значения функции F на отрезке я описывать не буду, потому что (а) мне лень, и (б) алгоритм очень схож с поиском ответа на запрос в обычном дереве Фенвика, только в нашем случае мы дополнительно используем встречное дерево Фенвика.

// Обновление произвольного элемента в массиве
void bit_update(int id, int val) {
	if(id&1) id=id^1, b[id] = r; // в зависимости от четности обновляем значение в нужном массиве
	else              a[id] = r;
	for(int j = ~1, t=2, z=1, p=id; ; z=z|t, t=t<<1) {
		j = j^t; const int v = id&j|z; if(v >= n) break;
		// При рассмотрении следующей вершины будем учитывать, что обе дочерние вершины
		// имеют одинаковый индекс, т.е. находить их явно, нам не надо.
		if(id&t) b[v] = F(a[p], b[p]);
		else     a[v] = F(a[p], b[p]);
		p = v;
	}
}

// Ответ на запрос
int bit_ask(int l, int r) {
	int res = NEUTRAL;
	for(; (r&r+1) >= l && r >= l; r=(r&r+1)-1)
		res = F(a[r], res);
	for(; (l|l-1) <= r && l && l < n; l=(l|l-1)+1) 
		res = F(b[l-1], res);
	return res;
}

Код RMQ с использованием данной структуры:

#include <stdio.h>

const int N = 1e5+7, MINF = -1e9;

int n, dx, m, a[N], b[N];

constexpr static int calc_dx(int n) {
	int dx = 1, tmp = 0; while((tmp = dx << 1) < n) dx = tmp;
	return dx;
}

int main() {
	scanf("%d", &n); dx = calc_dx(n);
	for(m = 1; m < n; m *= 2); m -= 2;
	for(int i = 0; i < n; ++i) {
		scanf("%d", &a[i]); if(i) b[i-1] = a[i];
	} b[n-1] = MINF;
	
	for(int i = 0, j; i < n; ++i) 
		if((j=i|i+1) < n && a[j] < a[i]) a[j] = a[i];
	for(int i = m-n+2; i < m; ++i) {
		const int j = i|i+1;
		const int u = m-i, v = m-j;
		if(j < m && b[v] < b[u]) b[v] = b[u];
	}

	for(scanf("%d", &m); m--; ) {
		char s[9]; int l, r;
		scanf("%s%d%d", s, &l, &r);

		if(s[0] == 'u') {
			int id = l-1;
			if(id&1) id=id^1, b[id] = r;
			else              a[id] = r;
			for(int j = ~1, t=2, z=1, p=id; ; z=z|t, t=t<<1) {
				j = j^t; const int v = id&j|z; if(v >= n) break;
				if(id&t) b[v] = a[p] > b[p] ? a[p] : b[p];
				else     a[v] = a[p] > b[p] ? a[p] : b[p];
				p = v;
			}
		}
		else {
			int res = MINF; --l; --r;
			for(; (r&r+1) >= l && r >= l; r=(r&r+1)-1)
				if(res < a[r]) res = a[r];
			for(; (l|l-1) <= r && l && l < n; l=(l|l-1)+1) 
				if(res < b[l-1]) res = b[l-1];
			printf("%d ", res);
		}
	}
}

P.S.: Сегодня протестировал свою программу на рандомных и не совсем рандомных тестах при различных ограничениях. По скорости сравнивал с этой реализацией ДО. Оказалось, что ДО все же быстрее, при большом количестве запросов разница достигает 100мс. Выводы можно делать разные, например oversolver предположил, что реализация встречного дерева Фенвика, где индексация будет начинаться не с нуля, а с единицы, может оказаться быстрее. Ну что ж, в ближайшее время постараюсь проверить.

Таблица с результатами: