Задача с Тинькофф стажировки.
Самая сложная задача с Тинькофф 2023.
Вам дается массив целых чисел а. Также дают q запросов, каждый запрос бывает двух видов
1) + l, r, x. Вы должны прибавить число х ко всем числам на отрезке l, r.
2) ? l, r, k, b. Вы должны найти max(min(a[i], k*i+b)).
n и q до 1е5.

Решение.
Давайте построим ленивое дерево отрезков на всем массиве, где в каждой вершине будем хранить максимум на всем отрезке.
И так наше дерево отрезков умеет прибавлять число х на отрезке, а также узнавать максимум на отрезке.
Давайте научимся обрабатывать второй запрос.
Вот вам дали l, r, k, b.
Путь mid_res=mid*k+b, где mid середина отрезка l, r.
Что вы можете сказать, если максимальное число из массива а на отрезке [mid, r] не меньше чем res_mid ?
Это означает, что ответ точно будет не меньше чем res_mid, значит отрезок [l, mid] вам не нужно рассматривать, так как на этом отрезке ответ будет точно меньше. Такой факт вам позволит не рассматривать одну из частей отрезка.

Теперь остается случай, когда максимальное число на отрезке [mid, r] меньше чем res_mid.
В такие моменты вам нужно запустить такое же решение на отрезке [l, mid] - которая вернет максимальный ответ, а на отрезке [mid, r] просто найти максимальное число. Далее вернуть максимум из этих двух чисел.
Замечу что находить максимум на отрезке вам поможет дерево отрезков.

Код в комментариях.