Олимпиадный тренинг

Задача . Башни 3.0


В компьютерной игре есть n башен, высота i-й башни равна ai метров. Определим расстояние между двумя башнями с индексами i и j как |i−j|. Разрешается прыгнуть с i-й башни на j-ю башню тогда и только тогда, когда не существует такого индекса 1 <= k <= n, такого, что расстояние от i-й до j-й башни не меньше расстояния от i-й башни до k-й башни, и k-я башня имеет большую высоту, чем j-я. Башня j достижима из башни i если существует последовательность корректных прыжков, которая начинается в i-й башне и заканчивается в j-й.
 

Вам даны q запросов вида (u,v,l,r). Для каждого запроса посчитайте количество индексов l <= k <= r, таких, что k-я башня достижима из u-й башни и из v-й башни. Обратите внимание, что во многих подзадачах выполняется ограничение u=vl=1r=n, то есть ответом на запрос будет общее число башен, достижимых из u .

 

Входные данные
Первая строка входных данных содержит одно целое число n (1 <= <= 500000) - количество башен.
Вторая строка входных данных содержит n чисел a1, a2, ..., an (1 <= a<= 109) - высоты башен.

Третья строка входных данных содержит одно целое число q (1 <= q  <= 500000) - количество запросов.

Следующие q строк описывают запросы. i-я из них описывает i-й запрос и содержит четыре целых числа uiviliri (1<= ui, vi <= n, 1 <= li <= ri <= n) - индексы вершин запроса и границы отрезка запроса.

 

Выходные данные

Выведите n чисел, i-е из которых должно быть равным ответу на i-й запрос.

 

Примечание

В первых двух примерах запросы спрашивают количество достижимых из каждой башни башен.

В первом примере с 1-й башни можно прыгнуть на башни 1 и 5. Любая другая башня имеет меньшую высоту, чем башня 1, поэтому туда нельзя прыгнуть (в качестве k можно выбрать 1). Множество достижимых из 1-й башни также состоит из башен 1 и 5. Со второй башни можно прыгнуть на башни 1, 2, и 5, они же являются множеством достижимых. С третьей башни можно прыгнуть на башни 2, 3, 5. Однако, башня 1 также является достижимой, поскольку можно сделать два прыжка: 3→2→1. Таким образом, получается 4 достижимые башни. С 4-й башни можно прыгнуть на башни 4 и 5, они же являются единственными достижимыми. Из 5-й башни достижима только она сама.

Во втором примере из 1-й и из 2-й башни достижимы башни 1,2,3,4,5. Из 3-й башни достижимы башни 3,4,5. Из 4-й и 5-й башни достижимы башни 4,5. Из 6-й башни достижимы башни 4,5,6. Из 7-й башни достижимы башни 4,5,6,7.

Рассмотрим третий пример:

  • В первом запросе множество индексов башен k на отрезке [l,r], достижимых из u и из v — {3,6}.
  • Во втором запросе множество индексов башен k на отрезке [l,r], достижимых из u и из v — {6}.
  • В третьем запросе множество индексов башен k на отрезке [l,r], достижимых из u и из v — {3}.
  • В четвёртом запросе множество индексов башен k на отрезке [l,r], достижимых из u и из v пусто.
  • В пятом запросе множество индексов башен k на отрезке [l,r], достижимых из u и из v — {6}.
 
Примеры
Входные данные Выходные данные
1
5
7 6 3 4 10
5
1 1 1 5
2 2 1 5
3 3 1 5
4 4 1 5
5 5 1 5
2
3
4
2
1
2
7
1 1 1 2 2 1 1
7
1 1 1 7
2 2 1 7
3 3 1 7
4 4 1 7
5 5 1 7
6 6 1 7
7 7 1 7
5
5
3
2
2
3
4
3
7
6 8 9 3 5 10 1
5
1 3 2 7
4 5 1 6
1 4 2 4
4 7 1 3
1 5 3 6
2
1
1
0
1

time 5000 ms
memory 512 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Python6
Комментарий учителя