Последовательность [b1, b2, ..., bk] называется битонической, если выполнены неравенства…
- User
Последовательность [b1, b2, ..., bk] называется битонической, если выполнены неравенства b1 < b2 < ... < bi > ... > bk для некоторого 1 ≤ i ≤ k. Например, последовательности [1], [1, 2, 3, 2], [1, 4, 10], [3, 2] являются битоническими, а последовательности [1, 1], [2, 1, 3] — нет. Задана последовательность [a1, a2, ..., an]. Требуется определить количество пар (l, r) таких, что 1 ≤ l ≤ r ≤ n и последовательность [al, al+1, ..., ar] является битонической. Входные данные Первая строка содержит число n (1 ≤ n ≤ 300 000). Вторая строка ввода содержит n целых чисел: a1, a2, ..., an (1 ≤ ai ≤ n). Выходные данные выведите одно число — количество пар (l, r), таких, что 1 ≤ l ≤ r ≤ n и последовательность [al, al+1, ..., ar] является битонической. Решение на c++, Оптимальное решение, которое будет работать при данных значениях за 1 секунду
- Assistant
Чтобы решить задачу определения количества битонических подотрезков в последовательности, воспользуемся следующей стратегией:
-
Определение Битонических Подотрезков:
- Битонический подотрезок - это такой подотрезок, который сначала строго возрастает, затем после некоторого пика строго убывает. Это включает в себя просто возрастающие и убывающие подотрезки, а также отдельные элементы.
-
Предварительные Вычисления:
- Для каждого элемента
iв последовательности вычислим два массива:left[i]— длина максимального строго возрастающего подотрезка, заканчивающегося вi.right[i]— длина максимального строго убывающего подотрезка, начинающегося вi.
- Для каждого элемента
-
Подсчет Битонических Подотрезков:
- Для каждого элемента
iколичество битонических подотрезков с пиком вiбудет равно произведениюleft[i] * right[i]. - Итоговый ответ будет суммой всех таких произведений для всех
iот1доn.
- Для каждого элемента
-
Реализация:
- Используем эффективный алгоритм с линейной временной сложностью
O(n), гдеn— размер последовательности. - Для хранения промежуточных значений используем 64-битные переменные, чтобы избежать переполнения при больших значениях.
- Используем эффективный алгоритм с линейной временной сложностью
Ниже представлена реализация на языке C++:
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> a(n); for(auto &x: a) cin >> x; vector<int> left_inc(n,1); for(int i=1;i<n;i++){ if(a[i] > a[i-1]){ left_inc[i] = left_inc[i-1] +1; } else{ left_inc[i] =1; } } vector<int> right_dec(n,1); for(int i=n-2;i>=0;i--){ if(a[i] > a[i+1]){ right_dec[i] = right_dec[i+1] +1; } else{ right_dec[i] =1; } } ll total =0; for(int i=0;i<n;i++){ total += (ll)left_inc[i] * (ll)right_dec[i]; } cout << total; } -