前缀和

//
// Created by Genes on 2020/9/15.
//
// 递增三元组
// 前缀和做法

#include<iostream>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

int n;
int cnt_a[N], cnt_c[N];
int s_a[N], s_c[N];
int a[N], b[N], c[N];
ll res;

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {// 前缀和从1开始
        cin >> a[i];
        cnt_a[a[i]]++;
    }

    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }

    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        cnt_c[c[i]]++;
    }
    s_a[0] = cnt_a[0];
    s_c[0] = cnt_c[0];

    // 处理前缀和
    for (int i = 1; i < N; i++) {
        s_a[i] = s_a[i - 1] + cnt_a[i];
        s_c[i] = s_c[i - 1] + cnt_c[i];
    }

    //遍历b数组
    for (int i = 1; i <= n; i++) {
        int B = b[i];
        res += (ll) s_a[B - 1] * (s_c[N - 1] - s_c[B]);
    }

    cout << res << endl;
    return 0;

}

双指针

// 递增三元组
// 双指针做法

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10;

typedef long long ll;

int a[N], b[N], c[N];
int n;
ll res;

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }
    sort(a, a + n);
    sort(b, b + n);
    sort(c, c + n);
    int j = 0, k = 0;
    for (int i = 0; i < n; i++) {
        int key = b[i];
        while (j < n && a[j] < key) j++;
        while (k < n && c[k] <= key) k++;
        res += (ll) j * (n - k);
    }
    cout << res << endl;
    return 0;
}

二分

//
// Created by Genes on 2020/9/14.
//
// 递增三元组

//优化版本
#include<iostream>
#include<algorithm>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;


int n;
int a[N], b[N], c[N];
long long int ans;

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }
    sort(a, a + n);
    sort(c, c + n);
    for (int i = 0; i < n; i++) {
        int key = b[i];
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (a[mid] < key) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }

        if (a[l] >= b[i]) {
            l = -1;
        }

        int cnt_a = l;
        l = 0, r = n - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (c[mid] > key) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        if (b[i] >= c[l]) {
            r = n;
        }

        int cnt_c = r;
        ans += (ll) (cnt_a + 1) * (n - cnt_c);
    }
    cout << ans << endl;
    return 0;
}

//暴力版本
//#include<iostream>
//
//using namespace std;
//
//const int N = 1e5 + 10;
//
//int n;
//int a[N], b[N], c[N];
//int res;
//
//int main() {
//    ios::sync_with_stdio(false);
//    cin >> n;
//    for (int i = 0; i < n; i++) {
//        cin >> a[i];
//    }
//    for (int i = 0; i < n; i++) {
//        cin >> b[i];
//    }
//    for (int i = 0; i < n; i++) {
//        cin >> c[i];
//    }
//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < n; j++) {
//            for (int k = 0; k < n; k++) {
//                if (a[i] < b[j] && b[j] < c[k]) {
//                    res++;
//                }
//            }
//        }
//    }
//    cout << res << endl;
//    return 0;
//}