Чтобы найти все натуральные делители числа $n$, перебираем $x$ от $1$ до $\sqrt n$: если $n$ делится на $x$, то делителями являются и $x$, и $n/x$.
Поэтому все делители находятся за $O(\sqrt n)$. Аналогично факторизация: перебираем $x$, пока $n$ делится на $x$ — записываем простой множитель. После перебора останется либо $1$, либо один большой простой делитель $> \sqrt n$ (такой может быть не более одного).
Задача. Дан массив длины $n$. Запросы двух типов:
add(l, r, x) — прибавить $x$ ко всем элементам отрезка $[l, r]$;sum(l, r) — сумма на отрезке $[l, r]$.Разобьём массив на блоки размера $K$ (последний блок может быть неполным). Для каждого блока храним две величины:
sum — сумму элементов блока (без учёта добавки);add — ленивую добавку, которую нужно прибавить ко всем элементам блока.add(l, r, x)Отрезок разбивается на три части: префикс, несколько полных блоков и суффикс.
add; так запрос стоит $O(K + n/K)$.sum соответствующего блока.add на $x$ (не трогая элементы).Сумма на отрезке: префикс/суффикс считаем по элементам, а для полного блока $j$ прибавляем $\text{sum}[j] + \text{add}[j] \cdot \text{len}[j]$.
При $n = 10^5$ это $\approx 300$–$900$ операций на запрос — «прибавление на отрезке» за $\sqrt n$ это очень хорошо.
const int K = 320; // размер блока ≈ sqrt(n); константа компилируется быстрее
void add(int l, int r, long long x) {
int bl = l / K, br = r / K;
if (bl == br) {
for (int i = l; i <= r; ++i) { a[i] += x; blockSum[bl] += x; }
return;
}
for (int i = l; i < (bl + 1) * K; ++i) { a[i] += x; blockSum[bl] += x; }
for (int b = bl + 1; b < br; ++b) blockAdd[b] += x; // ленивая добавка
for (int i = br * K; i <= r; ++i) { a[i] += x; blockSum[br] += x; }
}
long long sum(int l, int r) {
long long res = 0;
int bl = l / K, br = r / K;
if (bl == br) {
for (int i = l; i <= r; ++i) res += a[i] + blockAdd[bl];
return res;
}
for (int i = l; i < (bl + 1) * K; ++i) res += a[i] + blockAdd[bl];
for (int b = bl + 1; b < br; ++b) res += blockSum[b] + blockAdd[b] * K;
for (int i = br * K; i <= r; ++i) res += a[i] + blockAdd[br];
return res;
}int a[N] (быстрее вектора, меньше накладных расходов). Размер блока выносят в константу: компилятор заменяет деление на константу быстрыми операциями. При $n$ до $\sim 300$–$500$ тысяч корневая на массиве работает; при $10^6$ — уже на грани.Задача. В графе с $n$ вершинами и $m$ рёбрами посчитать количество треугольников (троек попарно соединённых вершин).
Идея. Назовём вершину лёгкой, если её степень $\le K$ (порядка $\sqrt m$), иначе тяжёлой.
Разделим треугольники на два случая:
Отсортируем вершины по возрастанию степени. Направим каждое ребро от вершины с меньшим индексом в сортировке к большей (то есть «вперёд»). Тогда:
Теперь у каждой вершины исходящих рёбер $O(\sqrt m)$. Считаем треугольники: для $v$ перебираем $u \in g[v]$, $w \in g[u]$ (оба по ориентированным рёбрам) и проверяем ребро $v$–$w$. Сложность $O(m\sqrt m)$.
Задача. Дан граф, во всех вершинах нули. Запросы:
add(v, x) — прибавить $x$ ко всем соседям вершины $v$;get(v) — узнать значение в вершине $v$.Решение (тяжёлые/лёгкие).
add проходим по всем её соседям и честно прибавляем $x$ к каждому.lazy[v]; при add(v, x) просто увеличиваем lazy[v].При get(v) нужно учесть два вклада:
Тяжёлых вершин $O(\sqrt m)$, поэтому суммирование по ним — быстрое.
add(v, x):
если v лёгкая: для каждого соседа u: base[u] += x
если v тяжёлая: lazy[v] += x
get(v):
ans = base[v]
для каждой тяжёлой h, соседней с v: ans += lazy[h]
return ansЗадача. Дана строка $T$ и запросы-строки $S_i$. Для каждой $S_i$ посчитать, сколько раз она встречается в $T$ как подстрока. Суммарная длина всех $S_i$ равна $L$.
Ключевое наблюдение. Различных длин среди строк $S_i$ немного:
Способ 1 (онлайн, хэши). Когда приходит строка длины $\ell$, которой ещё не было: выписываем хэши всех подстрок $T$ длины $\ell$ и кладём в map (или бор). Если длина уже была — просто смотрим в map. Суммарно получается $O(|T|\sqrt L)$ хэшей подстрок (различных длин $O(\sqrt L)$, для каждой — $O(|T|)$ подстрок), плюс $O(1)$ амортизированно на каждый запрос.
Способ 2 (бор). Для коротких строк ($\le \sqrt L$) можно построить бор всех их и искать; длинные строки ($> \sqrt L$) немногочисленны — их обрабатываем честно (например, префикс-функцией за $O(|S|+|T|)$).
Задача. Дан граф, вершины покрашены в белый/чёрный. Запросы: перекрасить вершину; найти и удалить любое ребро с концами разного цвета.
Это сложная задача. Основная идея — опять тяжёлые/лёгкие вершины:
Второе (безыдейное) решение — корневая на массиве. Перенумеруем рёбра так, чтобы почти все рёбра тяжёлой вершины шли подряд. Для каждого ребра храним бит «разноцветное». При перекраске вершины обновляем этот бит (для тяжёлой — отрезковым присваиванием, для лёгкой — точечно). Чтобы найти любое разноцветное ребро — держим по блокам бит «есть ли единичка в блоке» и ищем первый блок с единичкой, внутри — первое ребро. Всё за $O(\sqrt m)$.
Задача. Есть запросы «изменить значение в точке» и «сумма на отрезке». Все запросы известны заранее (оффлайн).
Идея. Разобьём последовательность запросов на блоки по $K$ штук. Обрабатываем блоки независимо:
Сложность: $O\!\left(\dfrac{q}{K} \cdot n + q \cdot K\right)$; при $K = \sqrt n$ — $O(q\sqrt n)$.
Задача. Дано дерево, все вершины белые. Запросы: покрасить вершину в чёрный; для вершины $v$ узнать расстояние до ближайшей чёрной.
Решение. Делим запросы на блоки по $K$:
Сложность: $\dfrac{q}{K}\cdot n + q \cdot K$. Чтобы выбрать $K$, приравниваем слагаемые:
Это следует из неравенства о средних: $x + y \ge 2\sqrt{xy}$. Для двух слагаемых $\dfrac{qn}{K}$ и $qK$:
То есть минимум суммы достигается, когда слагаемые равны, и правильный выбор — $K = \sqrt n$. Это работает при любом соотношении $n$ и $q$.
Задача. Дан массив и $q$ запросов «mex на подотрезке $[l,r]$». MEX — минимальное неотрицательное число, не встречающееся на отрезке.
Пусть есть структура данных $S$, которая хранит множество и умеет: (1) вычислять ответ, (2) добавлять/удалять элемент. Для mex можно поддерживать cnt[x] (сколько раз $x$ в множестве) и set отсутствующих чисел; mex — минимум этого set.
Расположим запросы (отрезки $[l_i, r_i]$) в некотором порядке. От запроса к запросу будем двигать границы $l$ и $r$, добавляя/удаляя элементы:
while (L > l) add(--L);
while (R < r) add(++R);
while (L < l) remove(L++);
while (R > r) remove(R--);
// ответ = текущее значение в структуре SСтоимость перехода от отрезка $[l_1,r_1]$ к $[l_2,r_2]$ равна $|l_2-l_1| + |r_2-r_1|$ — это манхэттенское расстояние между точками $(l_i, r_i)$ на плоскости. Нужно упорядочить точки так, чтобы суммарное расстояние было мало (задача коммивояжёра в манхэттенской метрике).
Возьмём $B$ и отсортируем запросы по паре $\left(\lfloor l/B \rfloor, r\right)$: сначала по номеру «полосы» по $l$, внутри полосы — по возрастанию $r$.
Оценка. Движение по $r$: внутри полосы суммарно $O(n)$, полос $n/B$, итого $O(n^2/B)$; между полосами ещё $O(n/B \cdot n)$. Движение по $l$: внутри полосы $\le B$ на переход, итого $O(qB)$.
Чтобы не возвращаться в начало каждой полосы, идём по нечётным полосам сверху вниз. Компаратор: домножаем $r$ на $(-1)^{\lfloor l/B \rfloor}$. Асимптотика та же, но константа сильно лучше.
Ещё более эффективный порядок — кривая Гильберта (гамильтонов путь по квадрату $2^k\times2^k$, обходящий все клетки). Есть функция hilbertOrder(x, y), вычисляющая номер клетки по координатам за $O(\log)$ битовыми операциями (рекурсивно по 4 подквадратам). Точки, соседние по номерам Гильберта, близки и по манхэттенскому расстоянию — константа ещё лучше (в 2–3 раза быстрее обычного Мо).
В алгоритме Мо запросов первого типа (вычислить ответ) — $q$, а второго (добавить/удалить) — $O(n\sqrt q)$. Значит, вычисление ответа можно позволить себе делать медленнее, чем добавление.
Для mex: разобьём массив cnt[0..n] на блоки размера $B$; для каждого блока храним, сколько в нём нулей. Добавление/удаление — $O(1)$; поиск минимального $x$ с cnt[x]==0 — находим первый блок с ненулевым числом нулей ($O(n/B)$), внутри блока — $O(B)$. Взяв $B=\sqrt n$, получаем mex за $O(\sqrt n)$, добавление за $O(1)$, итого $O(n\sqrt q)$.
Задача. На рёбрах дерева записаны числа; нужно отвечать на mex на пути между двумя вершинами.
Эйлеров обход. Делаем DFS, записывая вершину каждый раз, когда в неё заходим. Получится путь длины $2n-1$. Каждое ребро встречается в нём ровно два раза (туда и обратно).
Трюк с чётностью. Для пути от $s$ до $f$ возьмём первое вхождение $s$ и первое вхождение $f$ в Эйлеровом обходе. На получившемся подотрезке рёбра пути встречаются нечётное число раз, а все остальные — чётное (2 или 0). Поэтому, поддерживая в структуре только рёбра с нечётным количеством вхождений (добавление/удаление ребра меняет его «чётность»), мы получаем ровно рёбра пути.
Дальше — обычный алгоритм Мо по этому Эйлерову массиву длины $2n$.
Задача. В вершинах дерева записаны числа; для пути $s$–$f$ нужно посчитать количество инверсий в выписанной последовательности.
Сначала на массиве: инверсии на подотрезке считаем, поддерживая структуру (Фенвик/дерево отрезков) и добавляя/удаляя элементы только по краям. При добавлении элемента справа к ответу прибавляем количество чисел в множестве, больших его; слева — меньших.
Общий метод для дерева. Проблемы трюка с чётностью: числа на вершинах, а не рёбрах, и обновление «в середину» пути (не по краям). Решение — честно поддерживать текущий путь в деке:
Задача. Для каждого запроса $[l,r]$ посчитать, сколько элементов на отрезке являются префиксными максимумами (строго больше всех предыдущих).
Добавление справа — просто (сравниваем с текущим максимумом); удаление справа — тоже (стек максимумов). Но добавление/удаление слева требует удаления префикса стека — амортизированно, а в обычном Мо амортизация недопустима (откаты ломают оценку).
Мо с откатами. Обрабатываем блоки по $l$ по-отдельности. Для блока:
Сложность: $O\!\left(\dfrac{n}{B}\cdot n + qB\right)$; при $B=\sqrt n$ — $O((n+q)\sqrt n)$.
Если к запросам mex на подотрезке добавляются изменения в точке, вводим третью ось — «время». Каждый запрос кодируется тройкой $(l, r, t)$, где $t$ — номер версии массива (после $t$ изменений). Переход между версиями — это применение/откат одного точечного изменения (удалить старое значение, добавить новое) за $O(1)$.
Сортируем запросы по тройке $\left(\lfloor l/B \rfloor, \lfloor r/B \rfloor, t\right)$, где $B = n^{2/3}$:
Здесь плоскость $(l, r)$ разбивается на квадраты $B\times B$ («стаканы»); внутри стакана идём по возрастанию времени $t$. На практике полезна «змейка» по чётности координат.