Начало
Алгоритм Мо
Алгоритм Мо применяется для решения следующей задачи. Задан массив из N элементов, для которого выполняется M запросов на получение некоторой информации об элементах массива с lj-го по rj-й.
Ограничения алгоритма:
- массив не изменяется;
- информация может быть получена за O(N) последовательной обработкой элементов массива.
Алгоритм Мо позволяет обработать M запросов за O(N⋅√N+M⋅√N+M⋅log действий. Он является комбинированным алгоритмом, основанным на 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) действий.
