ABC371E I Hate Sigma Problems

Lotus_Land · 2024-09-15 07:32:43 · 题解

题意

给定一个长度为 N 的数列 A=(A_1,A_2,\dots,A_N)。定义 f(i,j) 为 (A_i,A_{i+1},\dots,A_j) 中不同元素的种类数。求 \sum\limits_{i=1}^{N}\sum\limits_{j=i}^{N}f(i,j)。

分析

I Hate Sigma Problems.

最近的 E 好像一次比一次简单了。

考虑枚举右端点。记 lst_{i} 为 i 这个数最后一次出现的位置。每次在右端加入一个数，对前面所有左端点的影响：对 1 到 lst_i 的位置没有影响，对 lst_{i}+1 到当前位置有影响。然后我就写了线段树，其实没必要。 统计答案并更新 lst_i。

int n;
int lst[N],a[N];
LL ans,sum;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        sum+=i-lst[a[i]];
        lst[a[i]]=i;
        ans+=sum;
    }
    cout<<ans;
    return 0;
}