原题链接

ACwing

思路

本题实际上可以看做是对数组中的每一个数，求出其左侧与右侧数字中大于或者小于其的元素个数。换而言之，需要维护为每一个元素维护好一个前缀和，但是如果使用朴素的前缀和实现，每一次更新需要线性的时间，故而不可取。

这时候，我们就要祭出树状数组这一高级的数据结构了。

简单说来，树状数组的核心点在于，将一个区间通过二进制分解，从而我们需要求解的任意区间可以变成次查询。你可能要说，使用朴素前缀和，我们只需要常数时间就可以完成一次查询！的确，不过朴素的实现方式，需要线性的时间完成前缀和的维护，而树状数组只需要时间即可。

实现

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
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;

typedef long long  ll;
const int N = 200000+10;
ll c[N];

ll a[N]; 
ll lles[N];
ll lmore[N];
ll rles[N];
ll rmore[N];

ll ask(int x){
    ll ans =0;
    for(;x;x-=x&-x){
        ans += c[x];
    }
    return ans;
}

void add(int x, int val){
    for(;x<=N;x+=x&-x){
        c[x] += val;
    }    
}



int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    
    for(int i=1;i<=n;i++){
        
        lles[i] = ask(a[i]-1);
        lmore[i] = ask(n)-ask(a[i]);
        add(a[i],1);
    }
    
    memset(c,0,sizeof(c));
    
    for(int i=n;i>=1;i--){
        rles[i] = ask(a[i]-1);
        rmore[i] =ask(n)- ask(a[i]);
        add(a[i],1);
    }
    
    ll v_ans = 0;
    ll cup_ans = 0;
    for(int i=2;i<n;i++){
        v_ans +=  lmore[i]*rmore[i];
        cup_ans += lles[i]*rles[i];
    }
    cout<<v_ans<<" "<<cup_ans;
    return 0;
}