Мо с изменениями

Обычный алгоритм Мо требует, чтобы массив не менялся: состояние окна должно меняться маленькими шагами, а изменение элемента ломает это. Ответы, посчитанные до изменения и после, относятся к разным массивам.

Починка неожиданно простая: добавить к запросу третью координату.

Время как координата

Пронумеруем изменения по порядку. Каждому запросу припишем время $t$ - сколько изменений произошло до него. Теперь состояние описывается тройкой $(l, r, t)$, и операций становится шесть: сдвинуть левую границу, сдвинуть правую, сдвинуть время - каждое в обе стороны.

Сдвиг времени - это применение или откат одного изменения:

struct Change { int pos, value; };

auto applyTime = [&](int i) {           // и применение, и откат
    Change& u = changes[i];
    if (curL <= u.pos && u.pos <= curR) { del(a[u.pos]); add(u.value); }
    std::swap(a[u.pos], u.value);       // обмен делает операцию обратной себе
};

Обмен вместо присваивания - главная строчка. После него та же самая функция откатывает изменение назад: в changes[i].value теперь лежит старое значение. Переход по времени в обе стороны пишется один раз:

while (time < query.t) applyTime(time++);
while (time > query.t) applyTime(--time);

Проверка «попадает ли изменённая позиция в текущее окно» обязательна: изменение вне окна на счётчики не влияет, но массив поменять всё равно надо - иначе последующий сдвиг границы прочитает не то значение.

Порядок обхода и размер блока

Сортируем по тройке: номер блока $l$, номер блока $r$, время.

std::sort(queries.begin(), queries.end(), [B](const Ask& x, const Ask& y) {
    int bx = x.l / B, by = y.l / B;
    if (bx != by) return bx < by;
    int rx = x.r / B, ry = y.r / B;
    if (rx != ry) return (bx & 1) ? rx > ry : rx < ry;
    return (rx & 1) ? x.t > y.t : x.t < y.t;
});

Оценка складывается из трёх слагаемых:

указатель	сколько ходит
левый	$O(qB)$
правый	$O(n^2 / B)$
время	$O(q \cdot n^2 / B^2)$

Третья строчка - потому что внутри пары блоков $(b_l, b_r)$ время движется монотонно, а таких пар $(n/B)^2$. Сумма минимальна при

$$B \approx n^{2/3}, \qquad \text{итого } O(n^{5/3}).$$

Сколько это на самом деле

Оценка $n^{5/3}$ выглядит безобидно, пока не подставишь числа:

$n$	$n\sqrt n$	$n^{5/3}$
$10^4$	$10^6$	$4{,}6 \cdot 10^5$
$10^5$	$3{,}2 \cdot 10^7$	$2{,}2 \cdot 10^8$
$2 \cdot 10^5$	$8{,}9 \cdot 10^7$	$6{,}8 \cdot 10^8$
$5 \cdot 10^5$	$3{,}5 \cdot 10^8$	$3{,}1 \cdot 10^9$

На $10^4$ версия с изменениями даже дешевле обычной - но там и без Мо всё проходит. А начиная с $2 \cdot 10^5$ разница становится решающей: если в задаче есть изменения и $n$ больше сотни тысяч, Мо скорее всего не тот инструмент.

Ограничения в условии - подсказка. Задача на Мо с изменениями почти всегда даёт $n$ и $q$ до $5 \cdot 10^4$, и это не случайность.

Подробнее про каркас: «Алгоритм Мо».