2019牛客多校第八场 B Beauty Values 基础dp+思维

链接：https://ac.nowcoder.com/acm/contest/888/B
来源：牛客网
 

题目描述

Gromah and LZR have entered the second level. There is a sequence a1,a2,⋯ ,ana_1, a_2, \cdots, a_na1​,a2​,⋯,an​ on the wall.

There is also a note board saying "the beauty value of a sequence is the number of different elements in the sequence".

LZR soon comes up with the password of this level, which is the sum of the beauty values of all successive subintervals of the sequence on the wall.

Please help them determine the password!

输入描述:

The first line contains one positive integer nn_{}n​, denoting the length of the sequence.

The second line contains nn_{}n​ positive integers a1,a2,⋯ ,ana_1, a_2, \cdots, a_na1​,a2​,⋯,an​, denoting the sequence.

1≤ai≤n≤1051 \le a_i \le n \le 10^51≤ai​≤n≤105

输出描述:

Print a non-negative integer in a single line, denoting the answer.

示例1

输入

复制

4
1 2 1 3

输出

复制

18

题目大意:给你一段序列,找出所有子区间的中含有多少种数字,并求和.

题目思路:一个基础的dp题目,推出状态转移就好了

f(i)=f(i-1)+i-(vis[num[i]]?vis[num[i]]:0)

公式怎么出来的呢?考虑 由1-i 如果 第i个数字出现过,那么他对前一个出现过的i维护的区间是没有贡献的,只有vis[i]-i有贡献.

如果没出现过肯定 是前面维护的 都+1:

#include <bits/stdc++.h>
#include <stdio.h>
#include<string.h>
#define E 2.718
using namespace std;
typedef  long long ll;
const ll INF=0x7f7f7f7f;
const int maxn=1e5+8;
const double eps=1e-10;
const ll mod=1000000007;
ll n,m,k;
ll num[maxn];
int vis[maxn];
ll dp[maxn];
int main()
{
   ll sum=0;
   scanf("%lld",&n);
   for(int i=1;i<=n;i++) scanf("%lld",&num[i]);
   for(int i=1;i<=n;i++)
   {
        dp[i]=dp[i-1]+i-(vis[num[i]]?vis[num[i]]:0);
        vis[num[i]]=i;
   }
   for(int i=1;i<=n;i++)
     sum+=dp[i];
   printf("%lld\n",sum);
   return 0;
}