ZigZagK的博客
[树状数组]2020 ICPC 小米 网络选拔赛热身赛 B【Beauty Values】题解
ZigZagK
2020年10月29日 20:05
ACM
查看标签

题目概述

求数列 $\{a_n\}$ 所有子区间不同数个数的和。

解题报告

套路题，令 $nxt_i$ 表示 $a_i$ 下一个和 $a_i$ 相同的位置。

对于一个 $R$ ，如果 $1\le i\le R$ 中 $nxt_i>R$ ，就说明 $a_i$ 是 $[1,R]$ 中最后一个 $a_i$ ，只要 $L\in[1,i]$ 那么 $a_i$ 都可以产生贡献，按顺序枚举 $R$ ，求 $\sum_{nxt_i>R}i$ 就好了。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=100000;

int n,a[maxn+5],nxt[maxn+5],lst[maxn+5];LL c[maxn+5],ans;

void Insert(int x,int y) {for (int i=x;i<=n+1;i+=i&-i) c[i]+=y;}
LL Sum(int x) {LL sum=0;for (int i=x;i;i-=i&-i) sum+=c[i];return sum;}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=n;i++) lst[i]=n+1;
    for (int i=n;i;i--) nxt[i]=lst[a[i]],lst[a[i]]=i;
    for (int i=1;i<=n;i++){
        Insert(n+1-nxt[i]+1,i);
        ans+=Sum(n+1-(i+1)+1);
    }
    printf("%lld\n",ans);return 0;
}
版权声明：本博客所有文章除特别声明外，均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处！