Добрый день, codeforces. Сегодня я хочу поделиться с вами одной задачей, которую я встретил в интернете и никак не могу решить, поэтому я решил обратиться к вам.
Задача
Ограничение времени: 3 секунды
Ограничение памяти: 256 мегабайт
Вам дан массив A из N натуральных чисел, а также вам даны Q запросов. Запросы бывают только одного типа: ? l r x — узнать сумму ⌊A[i] / x⌋, таким что (l <= i && i <= r) Ответьте на все эти запросы.
Входные данные
В первой строке входных данных задано число 1 <= N <= 100000 и 1 <= Q <= 2000000
Во второй строке вам даны n натуральных чисел 1 <= A[i] <= 20000
В строках с 3 по m + 2 строку даны запросы вида 1 <= l, r <= N и 1 <= x <= 1000000000
Нумерация массива идёт с одного.
Выходные файлы
Выведите ответ на каждый запрос в отдельной строке.
Примеры
Входные данные
10 5
10 5 1 3 10 14 15 8 19 11
1 10 2
5 7 100
2 3 2
4 7 3
9 10 1
Выходные данные
45
0
2
13
30
P.S.Разбора у данной задачи найти я не смог на сайте тоже нет.
Если x<корня из Макс числа, то у тебя остатков не больше корня. Предпосчитай остатки, тогда ответ (сумма на отрезке — cnt[i]*i), где cnt[i] — сколько раз на отрезке встречается остаток i. Если x>корня, то различных a[i]/x не больше корня(вернее они все <=корня). можно перебирать само значение, когда отвечаешь на запрос. Вроде перс ДО надо писать, чтобы ответить. Также сканлайном можно, пользуясь тем, что ответ можно считать, как f(r)-f(l-1).
Огромное спасибо за ваш ответ, надеюсь в скором времени напишу.
А можно ссылку на задачу? Хочу поиграться со всякими решениями, заодно узнаем, что задача не с соревнования, которое идёт (в гугле не нашёл задачу).
Ещё $$$Q$$$ до двух миллионов очень странно, может быть, до $$$200\,000$$$? Но неясно, как при копипасте мог добавиться 0.
Добрый вечер, я не копировал ни откуда данную задачу я свёл большую задачу к решению данной подзадачи, которую решить я не смог, но если вам интересно то я могу скинуть.
Здравствуйте, мне интересно!