KonanMentor's blog

By KonanMentor, 10 years ago, In Russian

Есть массив чисел. Как быстро отвечать на запросы

  • прибавить число на отрезке
  • узнать сколько раз число встречается на отрезке?

Пока что ничего быстрее не придумал.

Если кому интересно, идея sqrt-декомпозиции:

  • разобьем массив на блоков
  • для каждого блока будем хранить
    • cnt[x] — количество чисел x в блоке
    • delta — число, которое надо прибавить ко всем числам в этом блоке

Тогда на запрос прибавления числа D на отрезке будем отвечать так:

  • Если блок полностью входит в отрезок, то изменим его delta на D
  • Иначе пройдемся по элементам, которые лежат в границах запроса, и просто добавим к ним D

    cnt[a[i]] --;
    a[i] += D;
    cnt[a[i]] ++;
    

Запрос о количестве чисел X на отрезке:

  • Если блок полностью входит в отрезок, просто вернем cnt[X - delta]
  • Среди остальных элементов учтем те, которые равны X - delta
  • Vote: I like it
  • +8
  • Vote: I do not like it