Новый маршрут для трекинга
Сейчас самое время планировать новые трекинговые маршруты.
Опишем холмистую местность массивом из 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
Решить на C++
Сейчас самое время планировать новые трекинговые маршруты.
Опишем холмистую местность массивом из 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
Решить на C++
More Questions From This User See All
Answers & Comments
Ответ:
лол вроде же несложная задачка
Объяснение:
#include <bits/stdc++.h>
using namespace std;
int main () {
int n,m;
cin >> n >> m;
vector <int> a(n), p(n, 0);
for (int i = 0; i < n; i++)
cin >> a[i];
if (a[0] < a[1]) p[1] = 1;
for (int i = 2; i < n; i++) {
if (a[i - 1] < a[i]) p[i] = 1;
p[i] += p[i-1];
}
for (int i = 0; i < m; i++) {
int l, r;
cin >> l >> r;
cout << p[r - 1] - p[l - 1] << endl;
}
}