题解：Codeforces Round 960 (Div. 2) C

C. Mad MAD Sum

time limit per test: 2 seconds

memory limit per test: 256 megabytes

input: standard input

output: standard output

We define the \(\operatorname{MAD}\) (Maximum Appearing Duplicate) in an array as the largest number that appears at least twice in the array. Specifically, if there is no number that appears at least twice, the \(\operatorname{MAD}\) value is \(0\).

For example, \(\operatorname{MAD}([1, 2, 1]) = 1\), \(\operatorname{MAD}([2, 2, 3, 3]) = 3\), \(\operatorname{MAD}([1, 2, 3, 4]) = 0\).

You are given an array \(a\) of size \(n\). Initially, a variable \(sum\) is set to \(0\).

The following process will be executed in a sequential loop until all numbers in \(a\) become \(0\):

1. Set \(sum := sum + \sum_{i=1}^{n} a_i\);
2. Let \(b\) be an array of size \(n\). Set \(b_i :=\ \operatorname{MAD}([a_1, a_2, \ldots, a_i])\) for all \(1 \le i \le n\), and then set \(a_i := b_i\) for all \(1 \le i \le n\).

Find the value of \(sum\) after the process.

我们将数组中的 \(\operatorname{MAD}\) （最大重复出现数）定义为数组中至少出现两次的最大数字。具体来说，如果没有至少出现两次的数字， \(\operatorname{MAD}\) 的值就是 \(0\) 。

例如， \(\operatorname{MAD}([1, 2, 1]) = 1\) 、 \(\operatorname{MAD}([2, 2, 3, 3]) = 3\) 、 \(\operatorname{MAD}([1, 2, 3, 4]) = 0\) 。

给你一个大小为 \(n\) 的数组 \(a\) 。初始化变量 \(sum\) 设置为 \(0\) 。

下面的过程将依次循环执行，直到 \(a\) 中的所有数字都变成 \(0\) ：

1. 设置 \(sum := sum + \sum_{i=1}^{n} a_i\) ；
2. 设 \(b\) 为大小为 \(n\) 的数组。设 \(b_i :=\ \operatorname{MAD}([a_1, a_2, \ldots, a_i])\) 代表所有的 \(1 \le i \le n\) ，然后设 \(a_i := b_i\) 代表所有的 \(1 \le i \le n\) 。

求过程结束后 \(sum\) 的值。

Input

The first line contains an integer \(t\) (\(1 \leq t \leq 2 \cdot 10^4\)) — the number of test cases.

For each test case:

• The first line contains an integer \(n\) (\(1 \leq n \leq 2 \cdot 10^5\)) — the size of the array \(a\);
• The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq n\)) — the elements of the array.

It is guaranteed that the sum of \(n\) over all test cases will not exceed \(2 \cdot 10^5\).

输入

第一行包含一个整数 \(t\) ( \(1 \leq t \leq 2 \cdot 10^4\) ) - 测试用例的数量。

对于每个测试用例

• 第一行包含一个整数 \(n\) ( \(1 \leq n \leq 2 \cdot 10^5\) ) - 数组 \(a\) 的大小；
• 第二行包含 \(n\) 个整数 \(a_1, a_2, \ldots, a_n\) ( \(1 \leq a_i \leq n\) ) - 数组的元素。

保证所有测试用例中 \(n\) 的总和不超过 \(2 \cdot 10^5\) 。

Output

For each test case, output the value of \(sum\) in a new line.

输出

对于每个测试用例，在新行中输出 \(sum\) 的值。

Example

input

4
1
1
3
2 2 3
4
2 1 1 2
4
4 4 4 4

output

1
13
9
40

Note

In the first test case, \(a=[1]\) initially.

In the first loop:

1. Set \(sum := sum + a_1 = 0+1=1\);
2. Set \(b_1 :=\ \operatorname{MAD}([a_1])=\ \operatorname{MAD}([1])=0\), and then set \(a_1 := b_1\).

After the first loop, \(a=[0]\) and the process ends. The value of \(sum\) after the process is \(1\).

In the second test case, \(a=[2,2,3]\) initially.

After the first loop, \(a=[0,2,2]\) and \(sum=7\).

After the second loop, \(a=[0,0,2]\) and \(sum=11\).

After the third loop, \(a=[0,0,0]\) and \(sum=13\). Then the process ends.

The value of \(sum\) after the process is \(13\).

注

在第一个测试用例中， \(a=[1]\) 初始化。

在第一个循环中

1. 设置 \(sum := sum + a_1 = 0+1=1\) ；
2. 设置 \(b_1 :=\ \operatorname{MAD}([a_1])=\ \operatorname{MAD}([1])=0\) ，然后设置 \(a_1 := b_1\) 。

第一个循环后， \(a=[0]\) 和进程结束。进程结束后， \(sum\) 的值为 \(1\) 。

在第二个测试用例中，初始值为 \(a=[2,2,3]\) 。

第一个循环后， \(a=[0,2,2]\) 和 \(sum=7\) 。

第二个循环后， \(a=[0,0,2]\) 和 \(sum=11\) 。

第三次循环后， \(a=[0,0,0]\) 和 \(sum=13\) 。然后进程结束。

进程结束后， \(sum\) 的值为 \(13\) 。

我的题解
首先，我的赛时提交是一个假做法（数据弱了）
（我用的是计数pair + deque）
想看的可以看->链接 幸好是赛后hack

正解
大家可以打个表
打完表之后可以发现

• 第一次循环完之后，数组已经是单调的了，但是部分数字的个数还是只有 \(1\) 个
• 第二次循环完之后，数组已经把所有只有一个的数字清除掉了
  （每次循环记得更新 \(sum\) ）

于是，我们就可以遍历了，假设从 \(0\) 开始存储的数组，一直到 \(n-1\) ，遍历数组，对于第 \(i\) 个数字 \(a_i\)，\(sum\) 加上 \(a_i×(n-i)\)（ 如果是从 \(1\) 开始存储的那就是 \(a_i×(n-i+1)\) ）

这就是答案了

我的代码

#include <bits/stdc++.h>
#define int long long

const int N = 1e7 + 10;
int t;
int a[N];

void solve() {
    int n;
    std::cin >> n;
    for(int i = 1 ; i <= n ; i ++) std::cin >> a[i];
    int sum = 0;;

    for(int q = 0 ; q < 2 ; q ++){
        int mad = 0;
        std::map<int,int> mp;
        for(int i = 1 ; i <= n ; i ++) {
            sum += a[i];
            mp[a[i]] ++;
            if(mp[a[i]] > 1) mad = std::max(mad,a[i]);
            a[i] = mad;
        }
    }

    for(int i = 1 ; i <= n ; i ++) {
        sum += a[i] * (n-i+1);
    }
    std::cout  << sum << "\n";
}

signed main() {
    std::cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}