题目描述

解题思路

这个题目我们可以转换一些思维，我们主要求每个位置的左边，右边比她小的数字,两边的数字相乘就会得到最后的结果。然而求位置之后比她小的数字正好就是树状数组的功能。我们只需要维护一个y数组，也就是如果我们这个位置是y，那么y数组的y下标值+1。顺序遍历求y之前小于他的个数，那就是求y数组1-y-1的前缀和。

代码

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
50
import java.io.*;
import java.util.*;

class Main{
    public static int N = 200010,n;
    public static int[] a = new int[N],y = new int[N];
    public static long[] lower = new long[N],c = new long[N],greater = new long[N];
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    public static int lowbit(int x){
        return x & (-x);
    }
    
    public static long get(int x){
        long res = 0;
        for(int i = x;i > 0;i -= lowbit(i))
            res += c[i];
        return res;
    }
    
    public static void modify(int x,int k){
        for(int i = x;i <= n;i += lowbit(i))
            c[i] += k;
    }
    public static void main(String[] args)throws Exception{
        n = Integer.parseInt(br.readLine());
        
        String[] s = br.readLine().split(" ");
        for(int i = 1;i <= n;i++){
            a[i] = Integer.parseInt(s[i-1]);
            lower[i] += get(a[i] - 1);
            greater[i] += get(n) - get(a[i]);
            modify(a[i],1);
        }
        
        Arrays.fill(c,0);
        for(int i = n;i >= 1;i--){
            lower[i] *= get(a[i]-1);
            greater[i] *= (get(n) - get(a[i]));
            modify(a[i],1);
        }
        
        long resl = 0,resg = 0;
        for(int i = 1;i <= n;i++){
            resl += lower[i];
            resg += greater[i];
        }
        System.out.println(resg+" "+resl);
    }
}