Подумайте, как в этой задаче можно применить стек?

Вспомните решение через динамическое программирование за $$$O(nk)$$$.

Рассмотрите переходы в динамике

Подумайте как быстро совершать переход в динамике, чтобы получить решение за $$$O(n \log{k})$$$.

Вспомните задачу A. Подумайте как можно прикрутить сюда стек и находить минимум на отрезке за $$$O(1)$$$.

Рассмотрите $$$f(l, r) = \sum\limits_{l \le i \le r} a_i \cdot b_i$$$ на каком-то примере, выпишите первых пару слагаемых.

Как много раз значение $$$a_i \cdot b_i$$$ встретится в ответе? Оно встретится $$$i \cdot (n−i+1)$$$ раз.

Окей, теперь мы можем заметить, что для каждой позиции $$$i$$$ у нас есть значение $$$a_i \cdot b_i \cdot i \cdot (n−i+1)$$$ . Единственное переменное значение здесь — это $$$b_i$$$ . Пусть $$$val_i=a_i \cdot i \cdot (n−i+1)$$$ . \Заметьте, что вы не можете брать это значение по модулю 998244353 здесь, потому что тогда вы не сможете сравнивать эти значения правильно

Остается отсортировать массив $$$b$$$ и $$$val$$$ с собственным компаратором)

Вспомните бинарный поиск по ответу.

Это графовая задача.

Рассмотрите $$$dp[v, i]$$$ = предок вершины $$$v$$$ на расстоянии $$$2^i$$$.

$$$dp[v, 0]$$$ = предок. И $$$dp[v, j] = dp[ dp[v, j-1], j-1]$$$

Подумайте как при помощи этого массива дойти до любого предка вершины $$$k$$$.

К какому числу нужно сводить весь массив?

Как тут можно написать $$$dp$$$?

Используйте $$$dp[d]$$$ = минимальное число операций, чтобы получить один элемент со значением $d$.

Подумайте, можно ли посчитать количество единиц сразу для всех чисел, рассматривая не каждое число отдельно, а по разрядам.

Зафиксируйте некоторую битовую позицию $$$i$$$ (нумерация с нуля — младший бит $$$i=0$$$ и определите, как часто на этой позиции стоит $$$1$$$ в последовательности от $$$0$$$ до $$$n$$$.
Вспомните, что биты на позиции $$$i$$$ меняются по циклу длины $$$2^{i+1}$$$: сначала $$$2^i$$$ раз идут нули, потом $$$2^i$$$ раз — единицы, и так далее.

Подумайте, какой жадный алгоритм сюда можно прикрутить.

К какой сумме элементов множества $$$C$$$ и $$$B$$$ мы должны сводить.

Вспомните задачу о рюкзаке.