United Cows of Farmer John (USACO Gold 2021 US Open)

这是一个比较标准的区间问题，难度不大。

首先，naive的 $\mathcal{O}(n^2)$ 算法是比较容易想到的，就是扫描所有可能的窗口，维护窗口中间的数字集合（因为 $a[i] \leq n$ ，所以用数组就可以维护），然后看两个端点数字是否在中间出现过。

下面讨论怎样得到 $\mathcal{O}(n \log n)$ 的算法：

从左向右扫描 $r$ ，我们就是要数对于每个 $r$ ，有多少个 $l < r$ ，满足题目要求。
首先我们看到， $l$ 至少要比 $\text{lp}[r]$ 大， $\text{lp}[r]$ 定义为 $r$ 左侧使得 $a[\text{lp}[r]] = a[r]$ 成立的最大的下标。容易看到 $\text{lp}[r]$ 以及其左侧所有数字都不符合要求（包含和右端点相同的 $a[\text{lp}[r]]$ ），也就是说，我们要在 $(\text{lp}[r],r)$ 这个窗口里找有多少个合适的 $l$ 。
现在剩下的问题就是保证 $a[l]$ 不和 $(l,r]$ 区间中的数字相同，这个是个典型的区间问题：我们把 $\text{tree}[i]$ 定义成“ $[i+1,r]$ 里面至少存在一个值为 $a[i]$ ”，那我们要的答案就是 $(\text{lp}[r],r)$ 区间上这个为"否"的数量，是个区间求和的查询。
我们看怎样更新 $\text{tree}[i]$ ，每次 $r$ 向右移动一步的时候，我们可以看到最多更新一个值（ $\text{tree}[\text{lp}[r]] = 1$ ）。所以就是单点更新，区间求和。下面程序中使用线段树，当然用树状数组也是可以的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n;
int a[200005];
ll ans;
int lp[200005];         // "left pointer" to same value (or -1 if not found)
int tree[400005];       // tree[j]: [j+1,i]里面是否至少存在一个值为a[j]的元素
 
void set(int k, int x) {  // 更新元素k为x
    k += n;
    tree[k] = x;
    for (k /= 2; k >= 1; k /= 2) {
        tree[k] = tree[2*k]+tree[2*k+1];
    }
}
 
int sum(int a, int b) {
    a += n; b += n;
    int s = 0;
    while (a <= b) {
        if (a%2 == 1) s += tree[a++];
        if (b%2 == 0) s += tree[b--];
        a /= 2; b /= 2;
    }
    return s;
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    vector<int> last(n+1, -1);
    for (int i = 0; i < n; i++) {       // set lp[]
        lp[i] = last[a[i]];
        last[a[i]] = i;
    }
    for (int i = 1; i < n; i++) {
        int l = lp[i]+1, r = i-1;
        if (lp[i] >= 0)    
            set(lp[i], 1);
        ans += (r-l+1) - sum(l,r);
    }
    printf("%lld", ans);
    return 0;
}