calc - NekoMio's Blog

1.1 题目描述#

给定一个序列a，a 中任意两个元素都不等。如果i<j, 且a[i]<a[j]，则我们称a[i],a[j] 为一个顺序对，这个顺序对的值是指a[i+1],a[i+2]…….a[j-1] 中比a[i] 大，且比a[j] 小的数的个数。求一个序列中所有顺序对的值的和。

1.2 输入格式#

第一行n 然后n 个整数表示ai

1.3 输出格式#

一个整数，表示答案

1.4 Sample Input#

5
1 5 3 4 2

1.5 Sample Output#

1

1.6 数据范围及约定#

对于30% 的数据满足：1 <= n <= 300 对于另外30% 的数据满足：1 <= n <= 3000 对于100% 的数据满足，1 <= n <= 300000, 1 <= ai <= 10^9

题解#

反正挺伤心的没有想到正确的方向

对于每一个数他对后面的数所造成的贡献就是
他前面比他小的数的个数

然后树状数组维护一下就可以了

1
#include <cstdio>
2
#include <cstring>
3
#include <algorithm>
4
using namespace std;
5
long long Sum[2][300005];
6
#define lowbit(_) ((_) & (-_))
7
int n;
8
void add(int p, int x, int w)
9
{
10
    for (int i = x; i <= n; i += lowbit(i))
11
        Sum[p][i] += w;
12
}
13
long long Gsum(int p, int x)
14
{
15
    long long ans = 0;
16
    for (int i = x; i; i -= lowbit(i))
17
        ans += Sum[p][i];
18
    return ans;
19
}
20
int a[300005], Hash[300005];
21
int main()
22
{
23
    scanf("%d", &n);
24
    long long ans = 0;
25
    for (int i = 1; i <= n; i++)
26
    {
27
        scanf("%d", &a[i]);
28
        Hash[i] = a[i];
29
    }
30
    sort(Hash + 1, Hash + n + 1);
31
    int tot = unique(Hash + 1, Hash + n + 1) - Hash - 1;
32
    for (int i = 1; i <= n; i++)
33
        a[i] = lower_bound(Hash + 1, Hash + tot + 1,a[i]) - Hash;
34
    for (int i = 1; i <= n; i++)
35
    {
36
        int x = Gsum(0, a[i] - 1);
37
        add(0, a[i], 1);
38
        ans += Gsum(1, a[i] - 1);
39
        add(1, a[i], x);
40
    }
41
    printf("%lld\n", ans);
42
}