C-数颜色

题意

给出 个数，这 个数***有 个区间，对于每个区间求不同数字的个数，把所有区间的个数加起来，就得到了 。

分析

看了看数据，好像打表就行了。

我们怎么能暴力？

我要介绍的东西，叫前缀和。

什么是前缀和

• 前缀和可以简单理解为数列的前 项的和( )

• 前缀和是指给定一个数组，计算出一个新的数组，其中每个元素是原数组中该位置及其之前所有元素的和。

• 具体计算方法如下：

1. 初始化一个新数组prefix_sum，长度与原数组相同。
2. 将原数组的第一个元素复制到prefix_sum的第一个位置。
3. 从第二个位置开始遍历原数组，依次计算prefix_sum[i] = prefix_sum[i-1] + 原数组[i]。
4. 返回新数组prefix_sum作为结果。

• 例如，对于原数组[1, 2, 3, 4, 5]，计算出的前缀和数组为[1, 3, 6, 10, 15]。

• 前缀和的应用场景很多，例如可以用于高效计算数组中某个区间内元素的和。

( )

• 自行总结 ：一个预处理的过程，在输入时便把前面的数据（和，差，积等）算出来。

为什么本题能用前缀和

我们不难发现：在从 到 这个区间中，设有 个不同的数，如果数组中第 项不包含在这个区间中，则在第 到 ***有 个不同的数，否则这个区间中还是只有 个数。

代码实现时的困难

• :如果你认真看完了上一个标题，那么不禁会问：怎么前缀和？

• :使用一个二维数组 存储自 到 这个区间中不同的数的个数，从1到 读入 接着从1枚举 至 ,再用上一个标题下的方法前缀和预处理。

• :如何记录从 到 这个区间中不同数的个数？

• :用一个二维数组 记录在 后一个数是否存在。

什么，你还想要代码？

#include <bits/stdc++.h>
using namespace std;

const int N=1e6;
long long n,cnt;
long long a[N];

map<long long,map<long long,long long> > check;
map<long long,map<long long,long long> > sum;
//运用map防止数组爆炸 
//check为记录一个数是否存在 
//sum用于i~j的前缀和 


int main(){
	cin>>n;
	for(long long i=1;i<=n;i++){
		cin>>a[i];
		for(long long j=1;j<=i;j++){
			if(check[j][a[i]]==0){
				check[j][a[i]]=1;
				sum[j][i]=sum[j][i-1]+1;
			}
			else sum[j][i]=sum[j][i-1];
		}
	}
	//前缀和预处理 
	for(long long i=1;i<=n;i++){
		for(long long j=i;j<=n;j++){
			cnt+=sum[i][j];
		}
	}
	//把所有预处理的sum加起来 
	cout<<cnt;
	return 0;
}