Подразделы

Другие разделы

Дата и время

08/04/2020 07:19:15

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

printАлгоритм Мо

Алгоритм Мо применяется для решения следующей задачи. Задан массив из `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)` действий.
loading