11720. Джим и небоскребы

Задан массив h₁, h₂, ..., h_n. Подсчитайте количество пар индексов (i, j) (1 ≤ i < j ≤ n), для которых выполняются условия: h_i = h_j и .

Вход. Первая строка содержит одно целое число n (1 ≤ n ≤ 3 ⋅ 10⁵). Вторая строка содержит n целых чисел h₁, h₂, ..., h_n (1 ≤ h_i ≤ 10⁶).

Выход. Выведите количество пар индексов, удовлетворяющих указанным условиям.

Пример входа 1	Пример выхода 1
6 3 2 1 2 3 3	4
Пример входа 2	Пример выхода 2
10 5 3 5 3 2 3 1 3 5 5	9

РЕШЕНИЕ

стек

Анализ алгоритма

Представьте, что мы строим “стенки” из блоков одинаковой высоты.
Пара (i, j) образует “коридор”, если между этими стенками нет более высокой стены.

Для решения задачи будем использовать монотонный стек. Стек хранит пары (value, count):

· value – это высота стенки (значение h[i]).

· count – сколько подряд одинаковых элементов этой высоты уже встретилось, которые могут образовывать пары с будущими такими же элементами.

То есть:

· Для каждого “блока одинаковых чисел” мы запоминаем только два параметра: число и сколько раз оно уже подряд встретилось.

· Когда появляется новый элемент, мы можем сразу сказать, сколько пар он образует: это число ровно count для вершины стека.

Например, пусть текущее число равно a = 5, и ранее оно уже встречалось 3 раза (то есть на данный момент число a = 5 встречается четвертый раз). Предположим, что между всеми этими вхождениями числа a находятся только меньшие элементы. Тогда количество новых пар индексов (i, j), где j – текущий индекс и выполняется условие h_i = h_j = a, будет равно 3.

При обработке очередного числа h_i:

· Если число на вершине стека меньше h_i, то удаляем его из стека.

· Если число на вершине стека равно h_i и ранее оно встречалось x раз, то увеличиваем искомое количество пар индексов на x и обновляем число появлений h_i на x + 1.

· Если стек пуст или число на вершине стека больше h_i, то добавляем в стек пару (h_i, 1). Это означает, что текущее значение h_i встретилось первый раз (возможно, оно появлялось ранее во входной последовательности, но было удалено из стека из-за большего элемента).

Пример

Рассмотрим первый тест.

Реализация алгоритма

Читаем входные данные.

scanf("%d", &n);

vector<int> v(n);

for (i = 0; i < n; ++i)

scanf("%d", &v[i]);

В переменной res будем хранить количество найденных пар индексов.

res = 0;

Объявим стек пар.

stack<pair<int, int>> st;

Последовательно обрабатываем все числа массива.

for (i = 0; i < v.size(); i++)

{

Пока на вершине стека находится число, меньшее v[i], удаляем его из стека.

while (!st.empty() && st.top().first < v[i])

st.pop();

Если на вершине стека находится число, равное v[i], и оно встречалось ранее x раз (значение x хранится в st.top().second), то увеличиваем ответ res на x. После этого обновляем количество появлений v[i], заменив его на x + 1.

if (!st.empty() && v[i] == st.top().first)

{

res += st.top().second;

st.top().second += 1;

}

else

Если же число v[i] встретилось впервые, то добавляем в стек пару (v[i], 1).

st.push({ v[i], 1 });

}

Выводим ответ.

printf("%lld\n", res);