Нам дан массив размером N 1 <= N <= 1e5 с Ai положительными целыми числами, так что
1 <= Ai <= 1e9.
нам будет предоставлено Q запросов. 1 <= Q <= 1e5
Каждый раз, когда в запросе будет два целых числа, разделенных пробелами b c, 1 <= b,c <= N
Для каждого запроса нам нужно найти это Is moving from index b of array to index c of array possible ?, и если да, то мы нашли специальную сумму, которую я объяснил ниже.
Мы не можем просто перемещаться в массиве просто из индекса i to i+1, есть ограничение. Если мы хотим перейти от i to j, тогда A [j] должно быть строго больше, чем A [i], т.е. A[j] > A[i].
Обратите внимание на одну вещь: While moving we have to take the just next greater element than the current.
sum то, что нам нужно найти, - это сумма элементов, которые попали на путь, пройденный для достижения пункта назначения.
Например
массив: 3 2 5 4 6 6 7
запрос: 1 7
Итак, согласно запросу нам нужно перейти с 1-го если возможно, до последнего элемента.
Как мы видим, мы можем выбрать путь 3 --> 5 --> 6 --> 7 для достижения пункта назначения, а сумма будет 3+5+6+7 = 21
Но если последний элемент в массиве был 2
массив: 3 2 5 4 6 6 2
запрос : 1 7
Для этого запроса мы не можем достичь пункта назначения, поскольку после 6 целевой элемент 2 меньше его. Итак, для этого запроса NO answer exist.
Мой подход
Я знаю, что могу найти ответ в O(n), просто пройдя массив из A(b) to A(c) и узнав, что если ответ выйти или нет а также sum.
Но проблема в том, что запросов много, поэтому, если я использую решение O(n), сложность времени будет O(QN).
Ограничение по времени составляет всего 1 sec, поэтому мне нужно найти решение с постоянным временем O(c) для этого.
One Thing more С появлением запросов второго типа становится еще сложнее.
Тип запроса 2: в этом запросе нам нужно обновить значение по индексу с заданным K. запрос: b k, затем A[b] = K.
Кто-нибудь может мне помочь в этом ??