Beauty of Array————思维(或者DP)

心已赠人 2022-04-23 21:18 158阅读 0赞

# Beauty of Array #

Time Limit: 2 Seconds Memory Limit: 65536 KB  
Edward has an array A with N integers. He defines the beauty of an array as the summation of all distinct integers in the array. Now Edward wants to know the summation of the beauty of all contiguous subarray of the array A.

**Input**  
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

The first line contains an integer N (1 <= N <= 100000), which indicates the size of the array. The next line contains N positive integers separated by spaces. Every integer is no larger than 1000000.

**Output**  
For each case, print the answer in one line.

**Sample Input**  
3  
5  
1 2 3 4 5  
3  
2 3 3  
4  
2 3 3 2  
**Sample Output**  
105  
21  
38  
**Author**: LIN, Xi  
**Source**: The 12th Zhejiang Provincial Collegiate Programming Contest

--------------------

题目大意:自己翻译

这道题看一下数据范围就知道不能用 O ( n 2 ) O(n^2) O(n2)的写了  
于是想到找每一个数出现的次数，然后让这个数乘以它出现的次数，然后求和就OK

我们先来观察：  
对于一个没有重复数字数组，比如说

> a\[\] = \{1,2,3,4,5\}  
> 含1的有：1,12,123,1234,12345共5次  
> 含2的有：12,123,1234,12345,2,23,234,2345共8次  
> 含3的有：123,1234,12345,23,234,2345,3,34,345共9次  
> 含4的有：1234,12345,234,2345,34,345,4,45共8次  
> 含5的有：12345,2345,345,45,5共5次

设i从0开始  
我们可以发现，对于任意一个数字，它的出现次数等于 &ThickSpace; i ∗ ( n − i + 1 ) &ThickSpace; \\; i\*(n-i+1) \\; i∗(n−i\+1)比如3，它出现的次数是它的位置3\*(5-3+1)=9次，其它的数字也类似  
答案就是  1 ∗ 5 + 2 ∗ 8 + 3 ∗ 9 + 4 ∗ 8 + 5 ∗ 5 = 105 1\*5+2\*8+3\*9+4\*8+5\*5=105 1∗5\+2∗8\+3∗9\+4∗8\+5∗5=105  
对于没有出现重复数字的数组来说，我们这样的做法已经可以解决问题了，不过对于有重复数字的数组怎么办呢？

我们来继续观察

> a\[\] = \{2,3,3,2\}  
> 含第一个2的有： 2,23,233,2332共4次  
> 含第一个3的有： 23,233,2332,3,33,332共6次  
> 含第二个3的有：**233,2332,33,332**,3,32共6次  
> 含第二个2的有： **2332**,332,32,2共4次

可是我们对于重复出现的数字只统计一次就好了，请注意我加粗的部分，它们在之前已经出现过，当统计到第二个2或者3的时候，我们可以认为它们不需要被统计，因为当2或者3重复出现出现的时候，我们认为它已经被统计过了  
记pos\[x\]为x上一次出现的位置，pos\[x\]默认为0  
观察可以知道对于任意一个数字x，它的出现次数等于 &ThickSpace; ( i − p o s \[ x \] ) ∗ ( n − i + 1 ) &ThickSpace; \\; (i-pos\[x\])\*(n-i+1) \\; (i−pos\[x\])∗(n−i\+1)比如第二个3，它出现的次数是它的位置(3-2)\*(4-3+1)=2次，其它的数字也类似  
答案就是  2 ∗ 4 + 3 ∗ 6 + 3 ∗ 2 + 2 ∗ 3 = 38 2\*4+3\*6+3\*2+2\*3=38 2∗4\+3∗6\+3∗2\+2∗3=38

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int MAXN = 1e6+7;
    int pos[MAXN];
    int main()
    {
        
            int t,n,x;
            cin>>t;
            while(t--)
            {
        
                    cin>>n;
                    memset(pos,0,sizeof(pos));
                    ll ans = 0;
                    for(int i=1;i<=n;++i)
                    {
        
                            cin>>x;
                            ans += 1ll*(i-pos[x])*(n-i+1)*x;
                            pos[x] = i;
                    }
                    cout<<ans<<endl;
            }
            return 0;
    }

--------------------

我菜的一批