Я применял корневую декомпозицию. Поделил массив на \sqrt{n}. И начал в каждом блоке искать кол-во (i, j) пар. Если я правильно посчитал, то асимптотика всего этого будет O(n\sqrt{n}).
Как отвечать на запросы быстро?
Звучит как стандартная задача на МО, как раз ТЛ в 4 секунды. Более того здесь К это константа.
Это кстати базовая задача на sweepline mo вроде
upd: А нет, если в эту задачу добавить то что любимые числа это множество значений, то это будет базовой на sweepline mo
Ввел название задачи в гугле и тут же пошли туториалы 
Ну стоит всё таки посмотреть именно алгоритм Мо, если ты не смог решить эту задачу то скорее всего ты не знаешь этот алгоритм. А если знаешь то стоит закрепить его на стандартных задачах.
На алгоритм МО я 2-3 базовые задачи сдал, но sweepline mo настолько базовая тема? Просто не видел ее нигде(по крайней мере под таким названием).
Нужно в МОшке что-то дополнительно хранить, чтобы высчитывать пары [i, j]?
Это задача не на sweepline mo, я там в upd прописал то что расширенная версия этой задачи это базовая на sweepline mo.
В этой задаче в МОшке нужно хранить кол-во чисел x в множестве и текущий ответ для множества, очевидно как эти значения за O(1) пересчитывать при добавлении и удалении.
1 лайк
О, понял как писать. Спасибо за помощь