#1822. 区间计数

    ID: 1822 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1786来源:qoj.ac数据:公开样例枚举

区间计数

区间计数

题目描述

标题: 区间计数 - Problem - QOJ.ac

#8945. 区间计数

Statistics

题目描述

给定一个长度为 n 的整数序列 a1,a2,⋯,an,其中每个元素不小于 1、不大于 n,且 1 到 n 中每个数字最多出现两次。

称两个可重集合 S,T 相同当且仅当对于任意 x∈S∪T ,其在 S 和 T 中出现次数相同;反之,两个可重集合 S,T 不同当且仅当存在 x∈S∪T,其在 S 和 T 中出现次数不同。

称可重集合 S⊆{1,1,2,2,⋯,n,n} 合法当且仅当存在一个区间 [l,r] (1≤l≤r≤n),使得可重集合 T={al,al+1,⋯,ar} 和 S 相同。

你需要求出存在多少个不同的合法可重集合。

输入格式

从标准输入读入数据。

第一行包含一个正整数 n,表示序列长度。

第二行包含 n 个由空格隔开的正整数 a1,a2,⋯,an,描述序列。

输出格式

输出到标准输出。

输出一行一个整数,表示不同的合法可重集合数量。

样例

输入

5
1 2 3 1 3

输出

11

解释

合法可重集合有如下 11 种。

{1},{2},{3},{1,2},{1,3},{2,3},{1,3,3},{1,2,3},{1,1,2,3},{1,2,3,3},{1,1,2,3,3}。

样例

输入

12
1 2 3 4 5 6 5 6 4 3 2 1

输出

50

子任务

对于所有测试数据,1≤n≤5×105,1≤ai≤n。保证序列中每种数字出现不超过两次。

**Subtask 1 (5pts):**n≤100。

**Subtask 2 (15pts):**n≤5000。

**Subtask 3 (25pts):**n≤2×105,特殊性质 1。

**Subtask 4 (25pts):**n≤2×105,特殊性质 2。

**Subtask 5 (30pts):**无特殊限制。

**特殊性质 1:**ai 由另一序列 b1,b2,⋯,bn 进行如下变换而来:

  • 对于每个 1≤i≤n,独立均匀随机生成一个权值 pi∈[in−10−3,in+10−3]。
  • 序列 a 是由序列 b 按照权值 p 从小到大排序的结果。即对于每个 i∈[1,n],令 j 满足 pj 是 p1,p2,⋯,pn 中第 i 小的值,那么有 ai=bj。

**特殊性质 2:**保证 n 是偶数。保证 an2=n,且 a1,a2,⋯,an2 中的数字各不相同,an2,an2+1,⋯,an 中的数字也各不相同。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5
1 2 3 1 3
11

样例 2

12
1 2 3 4 5 6 5 6 4 3 2 1
50