Начало
Алгоритм Мо
Алгоритм Мо применяется для решения следующей задачи. Задан массив из `N` элементов, для которого выполняется `M` запросов на получение некоторой информации об элементах массива с `l_j`-го по `r_j`-й.
Ограничения алгоритма:
- массив не изменяется;
- информация может быть получена за `O(N)` последовательной обработкой элементов массива.
Алгоритм Мо позволяет обработать `M` запросов за `O(N*sqrt{N}+M*sqrt{N}+M*log\ M)` действий. Он является комбинированным алгоритмом, основанным на `sqrt`-декомпозиции, методе двух указателей и предварительной сортировке запросов.
Запросы делятся на группы, соответствующие интервалу, в который попадает левая граница запроса. Каждая группа соответствует интервалу из `sqrt{N}` элементов. Вначале запросы сортируются по номеру группы, в которую попадает левая граница, а при совпадении номеров групп – по правой границе:
int a[N];
struct query { int l,r,i; } q[M];
struct Mo_cmp {
int k;
Mo_cmp(int k):k(k){}
bool operator() (const query &a, const query &b)
{ return (a.l/k!=b.l/k) ? (a.l<b.l) : (a.r<b.r);
}
};
...
cin>>n>>m;
for(int i=0;i<n;++i) cin>>a[i];
for(int i=0;i<m;++i)
{ cin>>q[i].l>>q[i].r;
--q[i].l; --q[i].r;
q[i].i=i;
}
sort(q,q+m,Mo_cmp(sqrt(n)));
На следующем этапе для обработки упорядоченной последовательности запросов применяется метод двух указателей. Для каждого запроса производится перемещение концов интервала, пока они не совпадут с заданным и запоминание информации в массиве ответов. После обработки запросов полученные ответы выводятся. Пример программы для подсчета результатов по формуле `sum_{forall\ v\ in\ a_l…a_r}\ "count"^2(v)*v`, где `"count"(v)` – количество `v` среди `a_l…a_r`.
int answer[M];
struct state {
int l,r;
long long sum;
int c[MAX];
state():l(0),r(-1), sum(0) { fill(c,c+MAX,0); }
void change(int v, int d) {
sum-=(long long)c[v]*c[v]*v
c[v]+=d;
sum+=(long long)c[v]*c[v]*v;
}
void addLeft() { change(a[--l],1); }
void addRight() { change(a[++r],1); }
void delLeft() { change(a[l++],-1); }
void delRight() { change(a[r--],-1); }
int answer()const { return sum; }
} s;
...
state s;
for(int i=0;i<m;++i)
{ query qi=q[i];
while(s.l>qi.l) s.addLeft();
while(s.r<qi.r) s.addRight();
while(s.l<qi.l) s.delLeft();
while(s.r>qi.r) s.delRight();
answer[qi.i]=s.answer();
}
for(int i=0;i<m;++i) cout<<answer[i]<<"\n";
Анализ алгоритма. На сортировку уходит `O(M\ log\ M)` действий. На перемещение левого конца интервала будет использовано не более `O(M\ sqrt{N}+N)` действий. На перемещение правого конца интервала для каждой группы будет использовано не более `O(N)` действий, всего групп `sqrt{N}`, поэтому для всего набора запросов необходимо не более `O(N\ sqrt{N})`. Итого нужно `O(N*sqrt{N}+M*sqrt{N}+M*log\ M)` действий.
