← 返回题目列表

Codeforces · 2045/I

I. 微波子序列

中文机器翻译题面 查看原题

给你一个 $$$N$$$ 整数数组:$$$[A_1, A_2, \dots, A_N]$$$。

可以通过删除零个或多个元素而不更改剩余元素的顺序来从数组导出子序列。例如,$$$[2, 1, 2]$$$、$$$[3, 3]$$$、$$$[1]$$$ 和 $$$[3, 2, 1, 3, 2]$$$ 是数组 $$$[3, 2, 1, 3, 2]$$$ 的子序列,而 $$$[1, 2, 3]$$$ 不是数组 $$$[1, 2, 3]$$$ 的子序列数组 $$$[3, 2, 1, 3, 2]$$$。

如果子序列最多由两个不同的值组成并且每个元素与其相邻元素不同,则该子序列是可微波处理的。例如,$$$[2, 1, 2]$$$、$$$[3, 2, 3, 2]$$$ 和 $$$[1]$$$ 可以微波加热,而 $$$[3, 3]$$$ 和 $$$[3, 2, 1, 3, 2]$$$ 则不可微波加热。

将函数 $$$f(x, y)$$$ 表示为数组 $$$A$$$ 的最长微波子序列的长度,使得子序列中的每个元素要么是 $$$x$$$ 要么是 $$$y$$$。求所有 $$$1 \leq x < y \leq M$$$ 的 $$$f(x, y)$$$ 之和。

输入

第一行由两个整数 $$$N$$$ $$$M$$$ ($$$1 \leq N, M \leq 300\,000$$$) 组成。

第二行由 $$$N$$$ 整数 $$$A_i$$$ ($$$1 \leq A_i \leq M$$$) 组成。

输出

输出一个整数,表示所有 $$$1 \leq x < y \leq M$$$ 的 $$$f(x, y)$$$ 之和。

示例

输入 #1

5 4
3 2 1 3 2

输出 #1

13

输入 #2

3 3
1 1 1

输出 #2

2

注意

示例输入/输出#1 的说明

$$$f(1, 2)$$$ 的值为 $$$3$$$,取自子序列 $$$[2, 1, 2]$$$,该子序列可通过删除 $$$A_1$$$ 和 $$$A_4$$$ 获得。 $$$f(1, 3)$$$ 的值为 $$$3$$$,取自子序列 $$$[3, 1, 3]$$$,该子序列可通过删除 $$$A_2$$$ 和 $$$A_5$$$ 获得。 $$$f(2, 3)$$$ 的值为 $$$4$$$,取自子序列 $$$[3, 2, 3, 2]$$$,该子序列可通过删除 $$$A_3$$$ 获得。 $$$f(1, 4)$$$、$$$f(2, 4)$$$ 和 $$$f(3, 4)$$$ 的值都是 $$$1$$$。

示例输入/输出 #2 的说明

$$$f(1, 2)$$$ 和 $$$f(1, 3)$$$ 的值为 $$$1$$$,而 $$$f(2, 3)$$$ 的值为 $$$0$$$。