翻译/题解

农夫约翰的联合奶牛代表团
题目描述
农夫约翰的联合奶牛（UCFJ）要派遣一个代表团参加国际牛奥林匹克竞赛（IOI）。
共有 N 头奶牛参与代表团选拔（1≤N≤2⋅10……5），它们站成一排，第 i 头奶牛的品种为 bi​。
代表团必须由至少两头奶牛组成的连续区间构成 —— 即选择满足 1≤l<r≤N 的整数 l,r，代表选取第 l 头到第 r 头奶牛。所选区间最外侧的两头奶牛将被指定为领队。
为了避免品种冲突，每一位领队的品种，都必须与代表团中其他所有奶牛（包括另一位领队）的品种都不相同。
请你帮助 UCFJ 统计出合法的代表团选取方案总数。
输入格式
第一行：一个整数 N第二行：N 个整数 b1​,b2​,…,bN​（每个数的范围 [1,N]）
输出格式
输出一个整数，表示合法的代表团选取方案总数。注意：本题数据范围较大，需要使用 64 位整型（如 C++ 中的 long long）。

AC代码

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

typedef long long ll;
const int MAXN = 2e5 + 5;

// 树状数组：单点修改，区间查询
int tree[MAXN];
int n;
int b[MAXN];
int pre[MAXN], nxt[MAXN]; // 上一个/下一个同品种位置
int last[MAXN]; // 记录品种上一次出现的下标

// 树状数组更新
void update(int pos, int val) {
    for (; pos <= n; pos += pos & -pos)
        tree[pos] += val;
}

// 树状数组查询前缀和
int query(int pos) {
    int res = 0;
    for (; pos > 0; pos -= pos & -pos)
        res += tree[pos];
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> b[i];
    
    // 预处理 pre 数组：每个位置上一个同品种下标
    memset(last, 0, sizeof(last));
    for (int i = 1; i <= n; ++i) {
        pre[i] = last[b[i]];
        last[b[i]] = i;
    }
    
    // 预处理 nxt 数组：每个位置下一个同品种下标
    memset(last, n + 1, sizeof(last));
    for (int i = n; i >= 1; --i) {
        nxt[i] = last[b[i]];
        last[b[i]] = i;
    }
    
    ll ans = 0;
    // 枚举右端点 r，统计合法左端点 l
    for (int r = 1; r <= n; ++r) {
        // 条件：l > pre[r] 且 nxt[l] > r
        // 把当前 r 加入树状数组（标记可用）
        update(r, 1);
        // 如果 pre[r] 存在，移除它（不可用）
        if (pre[r]) update(pre[r], -1);
        
        // 统计区间 (pre[r], r-1) 内合法的 l 数量
        int L = pre[r] + 1;
        int R = r - 1;
        if (L <= R) {
            ans += query(R) - query(L - 1);
        }
    }
    
    cout << ans << endl;
    return 0;
}