Есть массив чисел. Как быстро отвечать на запросы
- прибавить число на отрезке
- узнать сколько раз число встречается на отрезке?
Пока что ничего быстрее не придумал.
Если кому интересно, идея sqrt-декомпозиции:
- разобьем массив на блоков
- для каждого блока будем хранить
- cnt[x] — количество чисел x в блоке
- delta — число, которое надо прибавить ко всем числам в этом блоке
Тогда на запрос прибавления числа D на отрезке будем отвечать так:
- Если блок полностью входит в отрезок, то изменим его delta на D
Иначе пройдемся по элементам, которые лежат в границах запроса, и просто добавим к ним D
cnt[a[i]] --; a[i] += D; cnt[a[i]] ++;
Запрос о количестве чисел X на отрезке:
- Если блок полностью входит в отрезок, просто вернем cnt[X - delta]
- Среди остальных элементов учтем те, которые равны X - delta