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

题解#

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

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

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

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
long long Sum[2][300005];
#define lowbit(_) ((_) & (-_))
int n;
void add(int p, int x, int w)
{
    for (int i = x; i <= n; i += lowbit(i))
        Sum[p][i] += w;
}
long long Gsum(int p, int x)
{
    long long ans = 0;
    for (int i = x; i; i -= lowbit(i))
        ans += Sum[p][i];
    return ans;
}
int a[300005], Hash[300005];
int main()
{
    scanf("%d", &n);
    long long ans = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        Hash[i] = a[i];
    }
    sort(Hash + 1, Hash + n + 1);
    int tot = unique(Hash + 1, Hash + n + 1) - Hash - 1;
    for (int i = 1; i <= n; i++)
        a[i] = lower_bound(Hash + 1, Hash + tot + 1,a[i]) - Hash;
    for (int i = 1; i <= n; i++)
    {
        int x = Gsum(0, a[i] - 1);
        add(0, a[i], 1);
        ans += Gsum(1, a[i] - 1);
        add(1, a[i], x);
    }
    printf("%lld\n", ans);
}