Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Блог пользователя josdas

Запросы сумма div x
Автор josdas, 10 лет назад, По-русски

Задан массив A и задаются запросы l r x. Ответ это где div операция целочисленного деления. Хочется увидеть решение онлайн. Не могли бы вы подсказать как решается эта задача? UPD: Всем спасибо за ответ!

  • Проголосовать: нравится
  • +19
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Умею за C*n предподсчета и ответ за log^2(n) * MAX_A / C (Видимо C должно быть ~ sqrt(log^2(n) * MAX_A)) Если q ~ n

Для всех X <= c префсуммы.

ДО. В каждом вершине все элементы. Далее запрашиваем префсуммами честную сумму, далее спрашиваем "склько чисел больше либо равны x?", "сколько больше либо равны 2х", на такой запрос легко отвечать за log^2(n).

→ Ответить
»
10 лет назад, # |
← Rev. 6   Проголосовать: нравится +13 Проголосовать: не нравится

Какие ограничения на A[i]? Если длина массива равна n, A[i] ≤ MAXA, то можно с предпосчётом за времени и памяти отвечать на запрос за : для x ≤ k предпосчитать суммы на префиксах, для x > k ответить на запросов вида "сколько чисел  ≤ t на отрезке" (решается за O(nlogn) времени и памяти для предпосчёта и O(logn) времени на запрос). Выбор k зависит от того, насколько жалко памяти и каково отношение числа запросов к n.

UPD. Надо обновлять страницу перед посылкой.

→ Ответить