Алгоритм Мо: различия между версиями
Глеб (обсуждение | вклад) |
KiKoS (обсуждение | вклад) м |
||
(не показаны 4 промежуточные версии 3 участников) | |||
Строка 29: | Строка 29: | ||
for(int j = 0; j < s_dec[i].a.size(); j++) { | 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; | int tl = s_dec[i].a[j].l, tr = s_dec[i].a[j].r; | ||
− | while (r > tr){ | + | while(r > tr) { |
− | + | r--; | |
ans -= a[r]; | ans -= a[r]; | ||
} | } | ||
Строка 49: | Строка 49: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | Подумаем над асимптотикой данного алгоритма, для каждого запроса левая граница пройдет не более, чем длину блока, но при этом правая граница идет только вперед, а следовательно для одного блока пройдет не более, чем длину массива, то есть суммарно алгоритм работает за $O( | + | Подумаем над асимптотикой данного алгоритма, для каждого запроса левая граница пройдет не более, чем длину блока, но при этом правая граница идет только вперед, а следовательно для одного блока пройдет не более, чем длину массива, то есть суммарно алгоритм работает за $O(M\sqrt{N} + M\sqrt{N})$, если размер блока - $\sqrt{N}$. |
Алгоритм Мо может помочь нам в ответе на гораздо более сложные вопросы - $k$-ая статистика на отрезке, медиана отрезка, наиболее встречающийся элемент на отрезке и так далее. | Алгоритм Мо может помочь нам в ответе на гораздо более сложные вопросы - $k$-ая статистика на отрезке, медиана отрезка, наиболее встречающийся элемент на отрезке и так далее. |
Текущая версия на 13:00, 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