Всем привет!

На контестах периодически попадаются задачи на запросы на отрезках. Большая часть задач даёт запросы в оффлайне, что даёт большую свободу действий, но всё же часто они сводятся к дереву отрезков, а иногда и алгоритму Мо. Однако иногда в задачах может оказаться так, что оффлайн её решает простой Мо, а в онлайне она становится интересной. В таких ситуациях некоторые люди пытаются поддерживать что-то типа $$$500$$$ разных состояний алгоритма Мо, я вообще не понимал, что имеется в виду.

Сегодня же я сумел придумать версию онлайн Мо, работающую за $$$O(n^{\frac{5}{3}})$$$ времени и памяти в нормальных задачах (в которых движение границ делается за $$$O(1)$$$). Для анализа асимптотики я буду считать, что $$$n = q$$$. Я не первый, кто такую идею придумал. Как оказалось, здесь и здесь было обсуждение, где такая идея была предложена, но я хочу сам о ней рассказать, потому что я о ней раньше не знал.

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

2043G - Задача на запросы

Тут слишком много всего наворочено — запросы изменения, да ещё и закодированы. Попробуем сначала решить версию оффлайн и без запросов обновления. Стоит оговориться, что я буду считать не количество индексов $$$i \lt j$$$ таких, что $$$a_i \neq a_j$$$, а наоборот, что $$$a_i = a_j$$$. Из этой величины легко получить ответ на исходную задачу, однако количество пар индексов с равными значениями поддерживать несколько проще.

Сама задача — несложное упражнение на алгоритм Мо.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define all(x) x.begin(), x.end()

const int N = 1e5 + 10;
const int B = 320; // roughly sqrt N
int a[N];
int cnt[N];
ll sum = 0;

void add(int v) {
    sum += cnt[v];
    cnt[v]++;
}

void del(int v) {
    cnt[v]--;
    sum -= cnt[v];
}

int L = 0, R = -1; // the pointers

void move(int l, int r) { // move pointers to the query point
    while (R < r) {
        ++R;
        add(a[R]);
    }
    while (R > r) {
        del(a[R]);
        R--;
    }
    while (L > l) {
        L--;
        add(a[L]);
    }
    while (L < l) {
        del(a[L]);
        L++;
    }
}

struct query {
    int l, r, i;
};

signed main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }
    int queries;
    cin >> queries;
    vector<query> q(queries);
    vector<ll> ans(queries);
    for (int i = 0; i < queries; i++) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        q[i] = {l, r, i};
    }
    sort(all(q), [&](const query &a, const query &b) {
        int al = a.l / B;
        int bl = b.l / B;
        if (al != bl)
            return al < bl;
        return a.r < b.r;
    });
    for (auto &[l, r, i] : q) {
        move(l, r);
        ans[i] = sum;
    }
    for (int i = 0; i < queries; i++)
        cout << ans[i] << ' ';
    cout << '\n';
    return 0;
}

Я хочу взглянуть на анализ асимптотики с геометрической стороны. Размер блока для алгоритма Мо обозначим за $$$B \approx \sqrt{n}$$$. Вкратце, мы делим плоскость на квадратики со стороной $$$B$$$ и обходим квадратики в правильном порядке.

Теперь добавим ограничение в виде онлайн запросов. К сожалению в этой версии мы не можем выбирать порядок обхода квадратиков, да и в каждый квадратик нам может понадобиться заходить несколько раз, поэтому нужен другой подход. Понятно, что лишь одной парой указателей нам не обойтись, поскольку в таком случае на каждый запрос мы будем отвечать за $$$O(n)$$$, что долго. Назовём состоянием всю необходимую информацию, которую мы обычно поддерживаем для одного отрезка. В данном случае это массив количеств $$$cnt$$$, количество пар равных индексов $$$sum$$$ и указатели $$$L$$$ и $$$R$$$. Я хочу создать несколько состояний, чтобы от какого-то из них можно было быстро дойти до нашего запроса.

Выберем $$$B \approx n^{\frac{2}{3}}$$$. Теперь у нас мало квадратиков, всего $$$\frac{n^2}{B^2} = n^{\frac{2}{3}}$$$. Я хочу сделать так, чтобы в каждом квадратике было состояние, чтобы от него было недалеко идти до очередного запроса. Действительно, внутри квадратика расстояние между точками не превосходит $$$2B$$$, а это уже приемлемое время работы для запроса. Алгоритм можно описать так:

Определим квадратик, в котором находится запрос.

• Если в нём ранее не было запросов, то можно за $$$O(n)$$$ инициализировать этот блок. Создадим состояние, например, в точке самого запроса.
• Иначе у нас есть состояние на расстоянии не более $$$2B$$$, поэтому мы можем за $$$O(B)$$$ ответить на запрос.

Так как блоков мало, суммарно все инициализации отработают за $$$O(n^{\frac{5}{3}})$$$, а суммарное количество движений указателей не превосходит $$$O(qB) = O(nB) = O(n^{\frac{5}{3}})$$$.

Отлично, мы научились делать Мо в онлайне быстрее чем за $$$O(nq)$$$. А можно ли прикрутить запросы изменения? И если да, то надо ли нам чем-либо жертвовать? Оказывается, ответы на эти вопросы — да и нет! Обычно при запросах изменения используется 3D Мо, который вводит время в качестве третьего измерения, и обходится уже не плоскость, а трёхмерное пространство. Тогда чтобы двигать третий параметр $$$T$$$, нужно проверить, лежит ли изменяемая позиция в текущем состоянии, и если да, то сделать del и add. Но нам ведь ничего не мешает сделать то же самое, просто для всех блоков. Поскольку их, опять же, мало, $$$O(n^{\frac{2}{3}})$$$, время работы никак не ухудшается.

С помощью такой идеи понятно, как развалить задачу. Да и пишется это довольно легко.

Моё решение: 329249141

Это просто феноменально, имхо, что настолько простая идея, как алгоритм Мо, может работать в онлайне, да ещё и с изменениями!

P. S.: Правда, как оказалось, это некоторая интерпретация разбора задачи, а не другое решение. Разбиение на квадратики — то же самое, что и разбиение на блоки. Инициализация состояния в каждом квадратике эквивалентна предпосчёту ответа для каждой пары блоков, а движение указателей — добавление элементов с краёв неполных блоков.