题意
输入整数n，再输入n个整数a1,a2,⋯ ,an，表示一段序列,求序列的所有子区间里面不同数字之和。
说明：
在序列1 2 1 3中，
区间 [1,1],[2,2],[3,3],[4,4]各含1个不同数字
区间 [1,2],[1,3],[2,3],[3,4]各含2个不同数字
区间 [1,4],[2,4]各含3个不同数字
故总和为：1×4+2×4+3×2=18
题解
Code
做法一：
枚举每个数字，算出每个数字对答案的贡献，最后把答案累加起来。qq[a]记录a的上一个位置，则a对答案的贡献是(i-qq[a])*(n-i+1)。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn=1e5+5; 5 ll n,a,qq[maxn]; 6 int main() 7 { 8 while(~scanf("%d",&n)) { 9 for(int i=1;i<=n;i++) 10 qq[i]=0; 11 ll ans=0; 12 for(int i=1;i<=n;i++) { 13 scanf("%lld",&a); 14 ans+=(i-qq[a])*(n-i+1); 15 qq[a]=i; 16 } 17 printf("%lld ",ans); 18 } 19 20 return 0; 21 }
做法二：
DP:for循环 i 遍历1-n，维护区间后端到 i 的区间的贡献dp[i]，最后将每个 i 的贡献累加起来就是答案。
状态转移：dp[i]=dp[i-1]+i-(vis[a[i]]?vis[a[i]]:0)
vis[a[i]]记录a[i]上一次出现的位置，如果该数a[i]出现过，那么它对前一个出现过的a[i]所维护的区间是没有贡献的，故当前a[i]只对区间 [k,i]（k∈(vis[a[i]], i]）有贡献。
如果a[i]前面没出现过，那么当前a[i]的贡献就是上一个的贡献+i。
1 #include<bits/stdc++.h> 2 typedef long long ll; 3 using namespace std; 4 const int maxn=1e5+8; 5 ll a[maxn],dp[maxn],n; 6 int vis[maxn]; 7 int main() 8 { 9 ll ans=0; 10 scanf("%lld",&n); 11 for(int i=1;i<=n;i++) scanf("%lld",&a[i]); 12 for(int i=1;i<=n;i++){ 13 dp[i]=dp[i-1]+i-(vis[a[i]]?vis[a[i]]:0); 14 vis[a[i]]=i; 15 } 16 for(int i=1;i<=n;i++) 17 ans+=dp[i]; 18 printf("%lld ",ans); 19 return 0; 20 }