问题理解

农夫约翰需要从 $N$ 头排成一行的奶牛中选出代表队参加国际牛学奥林匹克。代表队需要满足以下条件：

• 由至少三头奶牛的连续区间组成
• 选定三头领队，其中最边上的两头必须是领队
• 每名领队的品种必须与其他所有成员（包括其他领队）不同

我们需要计算满足条件的代表队数量。

关键观察

1. 领队位置约束：最左端和最右端的奶牛必须是领队，第三名领队可以在中间的任意位置
2. 品种唯一性：三名领队的品种必须在整个代表队区间内都是唯一的
3. 组合计数：同一个区间选择不同的领队组合算作不同的代表队

算法思路

核心思想

使用线段树维护每个位置作为左端点时，能够形成合法代表队的方案数。通过动态维护品种出现的位置信息，高效统计符合条件的区间。

数据结构设计

• 线段树：维护每个左端点的权值，支持区间加和区间查询
• 位置记录：
  • l[i]：品种 $b_i$ 上一次出现的位置
  • ll[i]：品种 $b_i$ 上上一次出现的位置
  • id[x]：品种 $x$ 最近一次出现的位置

算法流程

1. 初始化：读取输入数据，初始化线段树和位置记录数组
2. 扫描处理：从左到右扫描每个位置作为右端点：
   • 更新品种位置信息
   • 调整线段树中受影响的左端点
   • 查询当前能形成的合法代表队数量
   • 更新线段树状态
3. 输出结果：累加所有右端点对应的答案

复杂度分析

• 时间复杂度：$O(N \log N)$，每个位置处理时间为对数级别
• 空间复杂度：$O(N)$，使用线性额外空间

算法正确性

该算法通过动态维护每个品种的出现位置，确保在统计时只考虑品种唯一的领队组合。线段树的高效操作保证了在大数据规模下的可行性。

样例分析

输入

7
1 2 3 4 3 2 5

输出

9

解释

合法的代表队对应以下领队组合：

• $(1,2,3)$：区间 $[1,3]$，品种 $1,2,3$
• $(1,2,4)$：区间 $[1,4]$，品种 $1,2,4$
• $(1,3,4)$：区间 $[1,4]$，品种 $1,3,4$
• $(1,4,7)$：区间 $[1,7]$，品种 $1,4,5$
• $(2,3,4)$：区间 $[2,4]$，品种 $2,3,4$
• $(4,5,6)$：区间 $[4,6]$，品种 $4,3,2$
• $(4,5,7)$：区间 $[4,7]$，品种 $4,3,5$
• $(4,6,7)$：区间 $[4,7]$，品种 $4,2,5$
• $(5,6,7)$：区间 $[5,7]$，品种 $3,2,5$

每个组合都满足：

• 区间长度 ≥ 3
• 两端为领队
• 所有领队品种在区间内唯一

算法标签

• 数据结构

• 线段树

• 动态维护

• 组合数学

总结

本题通过巧妙的线段树应用，将复杂的组合计数问题转化为高效的数据结构维护问题。关键在于理解品种唯一性对区间选择的限制，以及如何动态维护这些约束条件。