Задача №114579. Башни 3.0
В компьютерной игре есть \(n\) башен, высота \(i\)-й башни равна \(a_i\) метров. Определим расстояние между двумя башнями с индексами \(i\) и \(j\) как \(|i - j|\). Разрешается прыгнуть с \(i\)-й башни на \(j\)-ю тогда и только тогда, когда не существует такого индекса \(1 \le k \le n\), такого, что расстояние от \(i\)-й до \(j\)-й башни не меньше расстояния от \(i\)-й башни до \(k\)-й, и \(k\)-я башня имеет большую высоту, чем \(j\)-я. Башня \(j\) достижима из башни \(i\) если существует последовательность корректных прыжков, которая начинается в \(i\)-й башне и заканчивается в \(j\)-й.
Вам даны \(q\) запросов вида \((u, v, l, r)\). Для каждого запроса посчитайте количество индексов \(l \le k \le r\), таких, что \(k\)-я башня достижима из \(u\)-й башни и из \(v\)-й башни. Обратите внимание, что во многих подзадачах выполняется ограничение \(u=v\), \(l=1\), \(r=n\), то есть ответом на запрос будет общее число башен, достижимых из \(u\) .
Первая строка входных данных содержит одно целое число \(n\) (\(1 \le n \le 500\,000\)) — количество башен.
Вторая строка входных данных содержит \(n\) чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_n \le 10^9\)) — высоты башен.
Третья строка входных данных содержит одно целое число \(q\) (\(1 \le q \le 500\,000\)) — количество запросов.
Следующие \(q\) строк описывают запросы. \(i\)-я из них описывает \(i\)-й запрос и содержит четыре целых числа \(u_i\), \(v_i\), \(l_i\), \(r_i\) (\(1 \le u_i, v_i, \le n\), \(1 \le l_i \le r_i \le n\)) — индексы вершин запроса и границы отрезка запроса.
Выведите \(n\) чисел, \(i\)-е из которых должно быть равным ответу на \(i\)-й запрос.
В первых двух примерах запросы спрашивают количество достижимых из каждой башни башен.
В первом примере с \(1\)-й башни можно прыгнуть на башни \(1\) и \(5\). Любая другая башня имеет меньшую высоту, чем башня \(1\), поэтому туда нельзя прыгнуть (в качестве \(k\) можно выбрать \(1\)). Множество достижимых из \(1\)-й башни также состоит из башен \(1\) и \(5\). Со второй башни можно прыгнуть на башни \(1\), \(2\), и \(5\), они же являются множеством достижимых. С третьей башни можно прыгнуть на башни \(2\), \(3\), \(5\). Однако, башня \(1\) также является достижимой, поскольку можно сделать два прыжка: \(3 \to 2 \to 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\}\).
Тесты к этой задаче состоят из десяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
Обозначим за \(C\) максимальную высоту башни.
| Группа | Баллы | n | C | q | Дополнительно | Зависимости |
| 0 | 0 | Тесты из условия | ||||
| 1 | 9 | \(n \le 100\) | \(C \le 10^9\) | \(q \le 1000\) | 0 | |
| 2 | 6 | \(n \le 2000\) | \(C \le 10^9\) | \(q \le 500\,000\) | Все \(a_i\) различны | |
| 3 | 7 | \(n \le 200\,000\) | \(C \le 2\) | \(q \le 100\,000\) | \(u_i=v_i\), \(l_i=1\), \(r_i=n\) | |
| 4 | 11 | \(n \le 200\,000\) | \(C \le 3\) | \(q \le 100\,000\) | \(u_i=v_i\), \(l_i=1\), \(r_i=n\) | 3 |
| 5 | 15 | \(n \le 10\,000\) | \(C \le 10^9\) | \(q \le 10\,000\) | \(u_i=v_i\), \(l_i=1\), \(r_i=n\) | |
| 6 | 18 | \(n \le 500\,000\) | \(C \le 10^9\) | \(q \le 500\,000\) | \(u_i=v_i\), \(l_i=1\), \(r_i=n\) | 3–5 |
| 7 | 12 | \(n \le 500\,000\) | \(C \le 10^9\) | \(q \le 500\,000\) | \(u_i=v_i\) | 3–6 |
| 8 | 5 | \(n \le 500\,000\) | \(C \le 10^9\) | \(q \le 500\,000\) | \(r_i \le \min(u_i, v_i)\) или | |
| \(l_i \ge \max(u_i, v_i)\) | 3–6 | |||||
| 9 | 11 | \(n \le 500\,000\) | \(C \le 10^9\) | \(q \le 500\,000\) | \(l_i=1\), \(r_i=n\) | 3–6 |
| 10 | 6 | \(n \le 500\,000\) | \(C \le 10^9\) | \(q \le 500\,000\) | Offline-проверка | 0–9 |
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
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
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