Алгоритм Мо: различия между версиями
м |
KiKoS (обсуждение | вклад) м |
||
Строка 53: | Строка 53: | ||
Алгоритм Мо может помочь нам в ответе на гораздо более сложные вопросы - $k$-ая статистика на отрезке, медиана отрезка, наиболее встречающийся элемент на отрезке и так далее. | Алгоритм Мо может помочь нам в ответе на гораздо более сложные вопросы - $k$-ая статистика на отрезке, медиана отрезка, наиболее встречающийся элемент на отрезке и так далее. | ||
− | Также существуют такие модификации алгоритма Мо, как [[Мо онлайн]], [[3-Д | + | Также существуют такие модификации алгоритма Мо, как [[Мо онлайн]], [[3-Д Мо]], [[Мо на деревьях]]. |
{{Автор|Глеб Лобанов|glebodin}} | {{Автор|Глеб Лобанов|glebodin}} | ||
[[Категория:Структуры данных]] | [[Категория:Структуры данных]] | ||
[[Категория:Конспекты]] | [[Категория:Конспекты]] |
Версия 12:59, 28 сентября 2020
Теперь обсудим еще одно решение задачи прибавления и суммы на отрезке. Допустим, что все запросы даны нам заранее и запросов обновления нет. Для каждого запроса закинем его в блок, где лежит его левая граница:
s_dec[l / s].a.push_back({l, r});
Затем внутри каждого блока отсортируем запросы по правой границе. Теперь давайте пройдемся по каждому блоку, поддерживая текущий отрезок, на который мы знаем ответ. И если текущий отрезок равен отрезку из запроса запоминать его, как ответ.
struct q {
int l, r, index;
};
struct block {
vector<q> a;
};
for(int i = 0; i < q; i++) {
s_dec[l / s].a.push_back({l, r, i});
}
for(int i = 0; i < s; i++) {
sort(all(s_dec[i].a), comp);
}
for(int i = 0; i < s; i++) {
int l = i * s, r = i * s;
int ans = 0;
for(int j = 0; j < s_dec[i].a.size(); j++) {
int tl = s_dec[i].a[j].l, tr = s_dec[i].a[j].r;
while(r > tr) {
r--;
ans -= a[r];
}
while(r < tr) {
ans += a[r];
r++;
}
while(l > tl) {
l--;
ans += a[l];
}
while(l < tl) {
ans -= a[l];
l++;
}
answ[s_dec[i].a[j].index] = ans;
}
Подумаем над асимптотикой данного алгоритма, для каждого запроса левая граница пройдет не более, чем длину блока, но при этом правая граница идет только вперед, а следовательно для одного блока пройдет не более, чем длину массива, то есть суммарно алгоритм работает за $O(M\sqrt{N} + M\sqrt{N})$, если размер блока - $\sqrt{N}$.
Алгоритм Мо может помочь нам в ответе на гораздо более сложные вопросы - $k$-ая статистика на отрезке, медиана отрезка, наиболее встречающийся элемент на отрезке и так далее.
Также существуют такие модификации алгоритма Мо, как Мо онлайн, 3-Д Мо, Мо на деревьях.
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin