Новый маршрут для трекинга

@Rorik · Регистрация: 28.06.2020

Студворк — интернет-сервис помощи студентам

Сейчас самое время планировать новые трекинговые маршруты.

Опишем холмистую местность массивом из n чисел. Высота i-го холма равна hi. Маршрут должен идти по k подряд идущим холмам (учитывая тот холм, с которого маршрут будет начинаться). Немолодым туристам не очень нравится, когда приходится много раз подниматься в гору — переходить с более низкого холма на более высокий.

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

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

В первой строке даны натуральные числа n, m (2≤n,m≤2⋅105) — общее количество холмов и количество запросов, соответственно.

Во второй строке даны n целых чисел hi(1≤hi≤105) — высоты холмов.

В следующих m строках записаны пары чисел lj и rj (1≤li≤rj≤n) — запросы на количество переходов с более низкого холма на более высокий на маршруте с началом в холме lj и завершением в rj.

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

Выведите m чисел — ответы на запросы.

Примеры
Ввод
Вывод
2 3
2 37
1 2
2 2
1 1
1
0
0

@Shamil1 · 06.07.2020, 10:23

Дерево отрезков.

Новые блоги и статьи Все статьи Все блоги /
Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а привычная функция main(). . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .
http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/

@Rorik 25 / 14 / 2 Регистрация: 28.06.2020 Сообщений: 50

	Новый маршрут для трекинга 04.07.2020, 16:04. Показов 1021. Ответов 1 Метки нет (Все метки) Сейчас самое время планировать новые трекинговые маршруты. Опишем холмистую местность массивом из n чисел. Высота i-го холма равна hi. Маршрут должен идти по k подряд идущим холмам (учитывая тот холм, с которого маршрут будет начинаться). Немолодым туристам не очень нравится, когда приходится много раз подниматься в гору — переходить с более низкого холма на более высокий. Помогите туристам определиться с выборам маршрута — напишите программу,которая отвечает на запросы о количестве переходов с более низкого холма на более высокий на данном маршруте. Входные данные В первой строке даны натуральные числа n, m (2≤n,m≤2⋅105) — общее количество холмов и количество запросов, соответственно. Во второй строке даны n целых чисел hi(1≤hi≤105) — высоты холмов. В следующих m строках записаны пары чисел lj и rj (1≤li≤rj≤n) — запросы на количество переходов с более низкого холма на более высокий на маршруте с началом в холме lj и завершением в rj. Выходные данные Выведите m чисел — ответы на запросы. Примеры Ввод Вывод 2 3 2 37 1 2 2 2 1 1 1 0 0 0

@Shamil1 Модератор 3134 / 2281 / 469 Регистрация: 26.03.2015 Сообщений: 8,877
	06.07.2020, 10:23
	Дерево отрезков. 0