Изначально у вас есть пустое множество прямых. Вам нужно обработать n запросов. Запросы могут быть такими:
• + k b — добавить прямую с уравнением y = kx + b.
• − k b — удалить прямую с уравнением y = kx+b. Гарантируется, что такая прямая существует.
• ? q — Найти количество прямых, которые пересекают прямую y = q в целочисленной точке x. (т.е те прямые для которых уравнение kx + b = q имеет целочисленное решение).(n,q,x,k<=3*10^5)
Давайте для i in [0..300000] поддерживать ответ на запрос типа ? i. Будем все это хранить в массиве ans.
При добавлении прямой kx + b изменяется примерное 300000 / k значений массива ans.
если k >= sqrt(300000), то в тупую обновим значения этого массива.
если k < sqrt(300000), то сделаем cnt[k][b % k]++. Таким образом у нас в массиве cnt будет поддерживаться количество запросов с такими k и b.
При удалении прямой делаем обратные действия.
При запросе:
Достаем из массива ans нужное значение + смотрим сколько прямых из массива cnt влияют на наш ответ
Ассимптотика O(n sqrt(N))
на этом будет ошибка
3
+2 3
? 1
На сколько я понял тут 2 запроса: + y = 2x + 3 ? y = 1
В зависимости от выбора порога, должно либо ans[1]++,
либо cnt[2][1]++.
Ответ на запрос(?) будет ans[1] + cnt[1][1] + cnt[2][1] + cnt[3][1] + ... = 1
так что это не похоже на контртест