关于充电宝的近10条评论(全部评论)

3754. 充电宝

★★ 输入文件：charger.in 输出文件：charger.out 简单对比
时间限制：1 s 内存限制：256 MiB

作为机器人，波特日常生活中没法找到充电插座，就需要充电宝维持运转。

一天，波特早上出门时，突然发现自己的电量严重不足。

波特有 $n$ 个充电宝，依次排成一排，第 $i$ 个充电宝的种类编号为 $a_i$。

波特可以拿上第 $l$ 个到第 $r$ 个充电宝，并且第 $l$ 个和第 $r$ 个充电宝必须和 $[l,r]$ 中的其它充电宝种类都不同。

平常波特可以用自己强大的大脑快速算出答案，但现在他的电量趋近于零，已经无法计算。

所以，请你帮忙算出波特有多少种拿充电宝的方案。

形式化题面

给定 $n$ 个正整数 $a_1,a_2,a_3,\ldots,a_n$

求满足 $a_l \neq a_{l+1\sim r},a_r \neq a_{l\sim r-1}$ 的 $[l,r]$ 的数量。

第一行一个整数 $n$。

第二行 $n$ 个正整数，第 $i$ 个数表示 $a_i$。

一个整数，表示取充电宝的方案数。

7
1 2 3 4 3 2 5

方案为：$[1,2],[1,3],[1,4],[1,7],[2,3],[2,4],[3,4],[4,5],[4,6],[4,7],[5,6],[5,7],[6,7]$

对于前 10% 的数据，$1\le n\le 100$。

对于前 20% 的数据，$1\le n\le 5\times 10^3$。

另有 10% 的数据，保证 $a$ 是 $1\sim n$ 的一个排列。

对于 100% 的数据，$1\le n\le 2\times 10^5,1\le a_i\le n$。

hasy-lgc