C2-F 2024-排序？数数！

题目描述

对于一个数组A=[a1,a2,a3,...an]A=[a_1,a_2,a_3,...a_n]​，定义

f(A)=∑i=0norder(ai)∙aif(A)=\sum_{i=0}^{n}order(a_i)\bullet a_i

其中

order(ai)=1+∑aj<ai 1≤j≤n1order(a_i)=1+\sum_{a_j<a_i\,1\leq j\leq n}1

给出随机数生成器

1
2
3
4
5
6
7
8
9
int nextRand() {
    static unsigned int rnd_num = 0x80000001;
    static int mod = 1e5 + 3;

    rnd_num ^= rnd_num >> 10;
    rnd_num ^= rnd_num << 9;
    rnd_num ^= rnd_num >> 25;
    return rnd_num % mod;
}

提示

一个数aia_i的orderorder定义为数组内全部元素比它小的数的个数加一。

题目分析

注意到aia_i在[0,1e5+2][0,1e5+2]中，可以考虑使用计数排序统计频率得到频率数组count，由于order的定义不包括当前数，所以再开一个数组count_before[i]用来存放小于i的数的总频率。最后通过f(A)=∑i=0n(count_before[a[i]]+1)∗a[i]f(A)=\sum_{i=0}^{n}(count\_before[a[i]]+1)*a[i]得到答案

  • f(A)f(A)较大注意使用long long

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 5000005

int nextRand()
{
    static unsigned int rnd_num = 0x80000001;
    static int mod = 100003;
    rnd_num ^= rnd_num >> 10;
    rnd_num ^= rnd_num << 9;
    rnd_num ^= rnd_num >> 25;
    return rnd_num % mod;
}
int a[N];
int main()
{
    int tt;
    scanf("%d", &tt);
    while (tt--)
    {
        int count[100100] = {0};
        int count_before[100100] = {0};
        int n;

        scanf("%d", &n);

        for (int i = 1; i <= n; i++)
        {
            a[i] = nextRand();
            count[a[i]]++;
        }

        for (int i = 1; i < 100100; i++)
        {
            count_before[i] = count_before[i - 1] + count[i - 1];
        }

        long long f_A = 0;
        for (int i = 1; i <= n; i++)
        {
            int order = count_before[a[i]] + 1;
            f_A += (long long)order * a[i];
        }
        printf("%lld\n", f_A);
    }
    return 0;
}