Автор задачи: Егор Юлин, разработчик: Константин Бац
Для решения этой задачи вспомним, как выглядит динамика для поиска наибольшей общей подпоследовательности: $$$$$$\mathtt{dp}_i = \max\limits_{i < j, a_i < a_j} \mathtt{dp}_j + 1 \text{,}$$$$$$ где $$$\mathtt{dp}_i$$$ соответствует длине НВП, заканчивающейся в $$$i$$$-м элементе.
От нас же по задаче требуется найти, во-первых, не длину максимальной подпоследовательности, а их количество (стандартное изменение пересчета динамики с $$$\max(\ldots)$$$ на $$$\mathrm{sum}(\ldots)$$$), а во-вторых, не просто возрастающих последовательностей, а сначала возрастающих, затем убывающих.
Стандартная идея, применимая в таких ситуациях — разбить искомые последовательности по «центральному» элементу. Заметим, что если перебирать $$$a_i$$$, слева от которого подпоследовательность возрастает, а справа — убывает, то ответ на задачу равен $$$$$$\sum\limits_{i = 1}^n \mathtt{\#lis}_i \cdot \mathtt{\#lds}_i \text{,}$$$$$$ где $$$\mathtt{\#lis}_i$$$ — число возрастающих подпоследовательностей, заканчивающихся в $$$a_i$$$, а $$$\mathtt{\#lds}_i$$$ — число убывающих подпоследовательностей, начинающихся в $$$a_i$$$.
Более того, заметим, что если мы научимся считать $$$\mathtt{\#lis}$$$, то $$$\mathtt{\#lds}$$$ можно просто посчитать как $$$\mathtt{\#lis}$$$ на развернутом массиве $$$a$$$.
Ну а для подсчета $$$\mathtt{\#lis}$$$ вспомним решение задачи о поиске НВП через дерево отрезков: будем обрабатывать элементы массива по очереди слева направо, а значения динамики $$$\mathtt{dp}_i$$$ хранить по индексу $$$a_i$$$. Тогда все элементы с $$$i < j$$$ и $$$a_i < a_j$$$ — это просто префикс нашего дерева отрезков. Поскольку мы хотим находить число подпоследовательностей, а не максимальную из них, пересчет будет выглядеть как $$$\mathtt{dp}_i = \sum\limits_{x < a_i} \mathtt{segment\_tree}_x$$$, то есть как запрос к ДО на префиксе.
Всего на подсчет $$$\mathtt{\#lis}$$$ и $$$\mathtt{\#lds}$$$ уйдет $$$\mathcal{O}(n \log n)$$$ времени, после чего ответ можно посчитать за линейное время, перебрав центральный элемент холма (см. формулу выше).