405 字
2 分钟
calc
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);}