Технокубок 2020 - Отборочный Раунд 1 |
---|
Закончено |
Давайте рассмотрим следующий процесс: изначально у вас есть пустой стек и массив $$$s$$$ длины $$$l$$$. Вы пытаетесь добавлять элементы массива в стек в порядке $$$s_1, s_2, s_3, \dots s_{l}$$$. Причем если стек пустой или элемент на вершине стека не равен текущему, то вы просто добавляете текущий элемент на вершину стека. Иначе вы не добавляете элемент и более того, удаляете верхний элемент стека.
Если после данного процесса стек окажется пустым, то массив $$$s$$$ считается стек-уничтожимым.
Примеры стек-уничтожимых массивов:
Давайте рассмотрим изменения стека более подробно при $$$s = [5, 1, 2, 2, 1, 4, 4, 5]$$$ (элемент на вершине текста выделен жирным шрифтом).
Вам задан массив $$$a_1, a_2, \ldots, a_n$$$. Вам нужно посчитать количество подотрезков этого массива, которые являются стек-уничтожимыми.
Обратите внимание, что вам нужно ответить на $$$q$$$ независимых запросов.
Первая строка содержит целое число $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — количество запросов.
Первая строка каждого запроса содержит единственное целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — длину массива $$$a$$$.
Вторая строка каждого запроса содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — элементы массива.
Гарантируется, что сумма $$$n$$$ по всем запросам не превосходит $$$3 \cdot 10^5$$$.
На каждый запрос выведите одно число — количество стек-уничтожимых подотрезков массива $$$a$$$.
3 5 2 1 1 2 2 6 1 2 1 1 3 2 9 3 1 2 2 1 6 6 3 3
4 1 8
В первом запросе есть четыре стек-уничтожимых подотрезка: $$$a_{1 \ldots 4} = [2, 1, 1, 2], a_{2 \ldots 3} = [1, 1], a_{2 \ldots 5} = [1, 1, 2, 2], a_{4 \ldots 5} = [2, 2]$$$.
Во втором запросе только один стек-уничтожимый подотрезок — $$$a_{3 \ldots 4}$$$.
В третьем запросе есть восемь стек-уничтожимых подотрезков: $$$a_{1 \ldots 8}, a_{2 \ldots 5}, a_{2 \ldots 7}, a_{2 \ldots 9}, a_{3 \ldots 4}, a_{6 \ldots 7}, a_{6 \ldots 9}, a_{8 \ldots 9}$$$.
Название |
---|