Джим та хмарочоси#11720

Джим та хмарочоси (Розбір)

Уявімо, що ми будуємо "стіни" з блоків однакової висоти.

Пара $(i, j)$ утворює "коридор", якщо між цими стінами немає більшої стіни. Для розв'язання задачі будемо використовувати монотонний стек. Стек зберігає пари $(v a l u e, co u n t)$ (value, count):

$v a l u e$ — це висота стіни (значення $h [i]$ ).
$co u n t$ — скільки підряд однакових елементів цієї висоти вже зустрілося, які можуть утворювати пари з майбутніми такими ж елементами.

Тобто:

Для кожного "блоку однакових чисел" ми запам'ятовуємо тільки два параметри: число і скільки разів воно вже підряд зустрілося.
Коли з'являється новий елемент, ми можемо одразу сказати, скільки пар він утворює: це число рівно $co u n t$ для вершини стека.

Наприклад, нехай поточне число дорівнює $a = 5$ a = 5, і раніше воно вже зустрічалося $3$ рази (тобто на даний момент число $a = 5$ a = 5 зустрічається четвертий раз). Припустимо, що між всіма цими входженнями числа $a$ знаходяться тільки менші елементи. Тоді кількість нових пар індексів $(i, j)$ , де $j$ — поточний індекс і виконується умова $h_{i} = h_{j} = a$ h_i = h_j = a, буде дорівнювати $3$ .

При обробці чергового числа $h_{i}$ h_i:

Якщо число на вершині стека менше $h_{i}$ h_i, то видаляємо його зі стека.
Якщо число на вершині стека дорівнює $h_{i}$ h_i і раніше воно зустрічалося $x$ разів, то збільшуємо шукану кількість пар індексів на $x$ і оновлюємо число появ $h_{i}$ h_i на $x + 1$ x + 1.
Якщо стек порожній або число на вершині стека більше $h_{i}$ h_i, то додаємо в стек пару $(h_{i}, 1)$ (h_i, 1). Це означає, що поточне значення $h_{i}$ h_i зустрічається перший раз (можливо, воно з'являлося раніше у входній послідовності, але було видалено зі стека через більший елемент).

Приклад

Розглянемо перший тест.

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

Читаємо вхідні дані.

scanf("%d", &n);
vector<int> v(n);
for (i = 0; i < n; ++i)
  scanf("%d", &v[i]);

У змінній $r es$ будемо зберігати кількість знайдених пар індексів.

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$ зберігається в $s t . t o p () . seco n d$ st.top().second), то збільшуємо відповідь $r es$ на $x$ . Після цього оновлюємо кількість появ $v [i]$ , замінивши його на $x + 1$ x + 1.

  if (!st.empty() && v[i] == st.top().first)
  {
    res += st.top().second;
    st.top().second += 1;
  }
  else

Якщо ж число $v [i]$ зустрілося вперше, то додаємо в стек пару $(v [i], 1)$ (v[i], 1).

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

Виводимо відповідь.

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