C++

$\color{gold}{— > 蓝桥杯辅导课题解}$

算法一：

思路：

双指针

$1、先sort一下a,b,c三个数组$

$2、然后遍历b数组，每次找到\ a数组中小于b[i]的数的个数s1\ 和\ c数组中小于等于b[i]的数的个数s2$

$3、res += (ll)s1 * (n - s2),\ 最后输出res即可$

$时间复杂度:O(n)$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

typedef long long ll;

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

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= n; i ++) cin >> b[i];
    for (int i = 1; i <= n; i ++) cin >> c[i];
    sort(a + 1, a + n + 1); sort(b + 1, b + n + 1); sort(c + 1, c + n + 1);

    int s1 = 0, s2 = 0;
    for (int i = 1; i <= n; i ++) {
        while (s1 < n && a[s1 + 1] < b[i]) s1 ++;
        while (s2 < n && c[s2 + 1] <= b[i]) s2 ++;
        res += (ll)s1 * (n - s2);
    }

    cout << res;

    return 0;
}

算法二：

思路：

二分

$1、sort一下a,b,c三个数组$

$2、遍历b数组，每次通过二分查找到\ a数组中小于b[i]的数的个数s1\ 和\ c数组中小于等于b[i]的数的个数s2$

$3、res += (ll)s1 * (n - s2)$

$时间复杂度:O(nlogn)$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

typedef long long ll;

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

int sa(int x) { // 查找数组a中小于x的数的下标/个数
    int l = 0, r = n;
    while (l < r) {
        int mid = l + r >> 1;
        if (a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

int sc(int x) { // 查找数组c中小于等于x的数的下标/个数
    int l = 0, r = n;
    while (l < r) {
        int mid = l + r >> 1;
        if (c[mid] > x) r = mid;
        else l = mid + 1; 
    }
    return l;
}

int main() {
    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); 

    ll res = 0;
    for (int i = 0; i < n; i ++) {
        int s1 = sa(b[i]);
        int s2 = sc(b[i]);
        res += (ll)s1 * (n - s2);
    }

    cout << res;

    return 0;
}

算法三：

思路：

前缀和

$通过as数组记录小于b[i]的个数，cs数组记录大于b[i]的个数$

$时间复杂度:O(n)$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

typedef long long ll;

int n;
int a[N], b[N], c[N];
int as[N]; // as[i]表示在a数组中有多少个数小于b[i]
int cs[N]; // cs[i]表示在c数组中有多少个数大于b[i]
int cnt[N], s[N];

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> a[i], a[i] ++;
    for (int i = 0; i < n; i ++) cin >> b[i], b[i] ++;
    for (int i = 0; i < n; i ++) cin >> c[i], c[i] ++;

    // 求as[]
    for (int i = 0; i < n; i ++) cnt[a[i]] ++;
    for (int i = 1; i < N; i ++) s[i] = s[i - 1] + cnt[i]; // 求cnt的前缀和
    for (int i = 0; i < n; i ++) as[i] = s[b[i] - 1];

    // 求cs[]
    memset(cnt, 0, sizeof cnt);
    memset(s, 0, sizeof s);
    for (int i = 0; i < n; i ++) cnt[c[i]] ++;
    for (int i = 1; i < N; i ++) s[i] = s[i - 1] + cnt[i];
    for (int i = 0; i < n; i ++) cs[i] = s[N - 5] - s[b[i]];

    // 枚举每个b[i]
    ll res = 0;
    for (int i = 0; i < n; i ++) res += (ll)as[i] * cs[i];

    cout << res;

    return 0;
}

$\small{分享：}$

$\large\color{blue}{— > C/C++输入字符串}$