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

РЕШЕНИЕ

стек

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

Объявим стек, который будет хранить пары: число и количество раз, которое это число встречалось ранее (до текущего момента). Например, пусть текущим числом является a = 5, и до текущего момента оно уже встречалось 3 раза. Предположим, что между всеми этими числами 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);