Сейчас вроде все ок

Надо найти такие F и S, что A <= F <= B && C <= S <= D && X <= F * S <= Y.
min(F, S) <= sqrt(Y) <= 10^6, значит можем перебрать. Перебираем F от A до min(A + 10^6, B). Надо найти S быстро, давайте распишем всё:

C <= S <= D

X <= F * S <= Y
X / F <= S <= Y / F

max(C, X / F) <= S <= min(D, Y / F)

Берем любой подходящий S, если таковы есть. (нету, если l > r).

Делаем тоже самое для S (перебираем S от C до min(C + 10^6, D), находим F за O(1)).

Да С интересно узнать

Задача С. Будем поддерживать дерево отрезков и сет. В дереве отрезков a[l] — будет означать количество различных чисел на отрезке [l..l+k-1]. Тогда get запрос на отрезке [l..r] это максимум на [l..r-k+1] в ДО. Запросы обновлений будем делать так: поддерживаем 10^6 сетов, set[x] — на каких позиция находится число х. При изменении числа x на у на позиции i нужно удалить из сета set[x] и добавить в set[y] позицию i. Также нужно поддержать актуальное состояние ДО: удаление/добавление позиции i из сета может повлиять на отрезок [i-k+1..i] в ДО (т.е для отрезков, которые начинаются в этих позиция элемент х пропадет/появится), но соседние элементы для i в сете (левый и правый) могут вносить свой вклад в эти отрезки, т.е. нужно взять отрезок [i-k+1..i] и убрать из него пересечение соседними элементами (обозначим получившийся отрезок [s..t])- это и будет отрезок, на котором удаление позиции i из сета уменьшит/увеличит количество различных чисел. Т.о просто прибавим/отнимем единицу в ДО на отрезке [s, t].

Задача Н. Для простоты будем решать задачу для каждого бита отдельно. Будем поддерживать дерево отрезков, в вершине которого будет храниться структура. (Это довольно стандартная техника, с которой можно познакомиться, например, на e-maxx, link). В структуре будем хранить три числа

1) ans — ответ на этом отрезке

2) t0 — какой будет ответ, если слева пристыковать отрезок, результат вычисления на котором будет 0

3) t1 — какой будет ответ, если слева пристыковать отрезок, результат вычисления на котором будет 1

Из всех функций (get, update) будем вовзращать не одно число, а такую структуру. Зная эту структуру для левого и правого сына можно посчитать эти величины для отрезка целиком.

К примеру, ans[v] = (ans[left] & t1[right]) | (~ans[left] & t0[right]) (если ans[left] = 1, то t1[right] — как раз ответ в результате, и наоборот, если ans[left] = 0, то t0[right] — ответ в результате).

По каждому биту решать задачу отдельно могло не пройти по тл, т.к. сложность такого решения была NK * log(N), поэтому нужно было хранить маску битов, т.е. ans, t0, t1 — это теперь не просто один бит, а K-битное число, и проделывать операции с ним. Такое решение работало за Nlog(N), что укладывалось в тл.

Задача К.

Пусть есть дерево с n вершинами. В нем всегда существует вершина, у которой размеры сыновей <=n/2. (Ну этот факт можно доказать, предлагаю сделать это самому).

Найдем эту вершины просто влоб за O(n). Предположим, что ответ проходит через эту вершину, тогда для этого случая найдем ответ за О(n) или О(NlogN). Если ответ не проходит через эту вершину, запустимся от каждого сына, и найдем в нем такую же вершину и проделаем то же самое. И так далее. Это займет NlogN времени. Этот подход мит ин зе мидл на дереве, или по другому — центроидная декомпозиция.

Как решать задачу для вершины v, через которую проходит ответ за O(n)? Под фразой "ответ проходит через вершину v" имеется ввиду, что она является lca вершин, которые являются ответом.

Предподсчитаем расстояние от v до всех вершин. Отсортируем все вершины дерева по a[u] и будем рассматривать вершины в порядке убывания a[u]. Зафиксируем некоторое a[u], пусть это и есть нам минимум из двух вершин, тогда из уже просмотренных вершин (для которых значение a[i] больше) нужно выбрать самую удаленную вершину, которая не лежит в одном поддереве вершины v с вершиной u (т.е. чтобы веришна v действительно являлась лца этих двух вершин). Для этого достаточно хранить две наиболее удаленные вершины от v, которые лежат в разных поддеревьях v, и обновлять эти два максимума. Если вершина u лежит в поддереве с вершиной с максимальным расстоянием, то возьмем тогда вторую по удаленности вершину, иначе первую по удаленности.

Кто может объяснить авторское решение?

Поскольку автор комментария выше участвовал в усложнённом контесте, предположу, что речь о нём. Одно решение выше уже привели, я опишу своё (схожее, но слегка другое и всё-таки O(k * n * log(n)), хотя наверняка битмасками можно дооптимизировать до O(n * log(n))):

Будем решать задачу для каждого бита отдельно, благо все операции побитовые. Заметим, что, по законам де Моргана,

f(a1) = a1
f(a1, a2) = !(a1 && a2) = !a1 || !a2
f(a1, a2, a3) = !((!a1 || !a2) && a3) = a1 && a2 || !a3
f(a1, a2, a3, a4) = !a1 || !a2 && a3 || !a4
f(a1, a2, a3, a4, a5) = a1 && a2 || !a3 && a4 || !a5
...

(i-ая строчка — отрицание (i-1)-й || !a_i)

Если не обращаем внимание на a1, то все остальные члены чередуют a_i и !a_i, а также чередуется оператор, причём так, что после || всегда есть !, а после && — нет.

Обратим внимание, что x && 1 == x и x || !1 == x, т.е., если один из a_i является единицей, то операция с её участием не меняет значения выражения. В свою очередь, x && 0 == 0 и x || !0 == 1, т.е. ноль всегда меняет значение выражения на значение, зависящое только от того, стоит ли этот ноль после || или &&, или, эквивалентно, от чётности позиции этого нуля.

Из этого получаем такое решение: строим дерево отрезков, в вершине храним чётность последней позиции, на которой в стоит ноль (или какой-то маркер на случай, если на отрезке нет ни одного нуля). Когда нужно посчитать f(a_l, ..., a_r), просто высчитываем первый член выражения (a_l или !a_l), а потом проверяем, есть ли среди a_l+1, ..., a_r хоть один ноль — если он есть, то смотрим на его чётность, определяем, стоял ли перед этим нулём || или &&, и заменяем ответ на соответствующее значение.

Ты кинул ссылку на третью олимпиаду в пост про вторую. Если третью хотел, то вот коммент