CF Round 808 Div.1 E

https://codeforces.com/contest/1707/problem/E
Приятная милая задача с очень натуральным условием.

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

Сразу можно убрать какие-то легкие случаи когда запрос и так уже = [1, n] или запрос длины 1. Легко заметить, что если ответ != -1, то можно сделать бинпоиск (если в массиве есть и единичка, и n, то очевидно, что бинпоиск работает).

Задачу стоит немного поисследовать. Давайте посмотрим на отрезки [l1, r1] и [l2, r2], которые пересекаются (i.e. max(l1, l2) <= min(r1, r2)). Тогда утверждается, что f(l1, r1) тоже пересекается с f(l2, r2). Доказательство: Пусть m = max(l1, l2). Заметим, что a[m] \in f(l1, r1) && a[m] \in f(l2, r2). Доказали.

Тогда это можно обобщить и понять, что:

• f(l, r) = union(f(l, l+1), f(l+1, l+2), ..., f(r-1, r))

а также:

• f^k(l, r) = union(f^k(l,l+1), f^k(l+1,l+2), ..., f^k(r-1,r))

Вот по сути и все, осталось насчитать f^k(i,i+1) и написать бинпоиск.

Код: https://codeforces.com/contest/1707/submission/217640127

Эта задача нас учит тому, что стоит больше исследовать даже какие-то простые идеи.