Nguồn: Đề thi Blue Bridge Cup tỉnh

Mô tả bài toán

Cho ba mảng số nguyên:

A = [A₁, A₂, ..., Aₙ]
B = [B₁, B₂, ..., Bₙ]
C = [C₁, C₂, ..., Cₙ]

Đếm số bộ ba (i, j, k) thỏa mãn:

1 ≤ i, j, k ≤ N
Aᵢ < Bⱼ < Cₖ

Định dạng nhập

• Dòng 1: Số nguyên N
• Dòng 2: N số nguyên A₁...Aₙ
• Dòng 3: N số nguyên B₁...Bₙ
• Dòng 4: N số nguyên C₁...Cₙ

Định dạng xuất

Một số nguyên duy nhất là kết quả.

Giới hạn dữ liệu

1 ≤ N ≤ 10⁵
0 ≤ Aᵢ, Bᵢ, Cᵢ ≤ 10⁵

Ví dụ

Nhập:
3
1 1 1
2 2 2
3 3 3

Xuất:
27

Phương pháp: Với mỗi phần tử Bⱼ, đếm số phần tử trong A nhỏ hơn Bⱼ và số phần tử trong C lớn hơn Bⱼ. Tổng số bộ ba hợp lệ là tích hai giá trị này.

Giải pháp 1: Tổng tiền tố

#include<iostream>
#include<cstring>
using namespace std;

typedef long long LL;
const int MAX = 100010;
int arrA[MAX], arrB[MAX], arrC[MAX];
int cntA[MAX], cntC[MAX], temp[MAX];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arrA[i], arrA[i]++;
    for (int i = 0; i < n; i++) cin >> arrB[i], arrB[i]++;
    for (int i = 0; i < n; i++) cin >> arrC[i], arrC[i]++;

    // Đếm phần tử trong A
    for (int i = 0; i < n; i++) temp[arrA[i]]++;
    for (int i = 1; i < MAX; i++) temp[i] += temp[i - 1];
    for (int i = 0; i < n; i++) cntA[i] = temp[arrB[i] - 1];

    memset(temp, 0, sizeof temp);

    // Đếm phần tử trong C
    for (int i = 0; i < n; i++) temp[arrC[i]]++;
    for (int i = 1; i < MAX; i++) temp[i] += temp[i - 1];
    for (int i = 0; i < n; i++) cntC[i] = temp[MAX - 1] - temp[arrB[i]];

    LL result = 0;
    for (int i = 0; i < n; i++) result += (LL)cntA[i] * cntC[i];
    cout << result;
}

Giải pháp 2: Tìm kiếm nhị phân

#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;
const int MAX = 100010;
int arrA[MAX], arrB[MAX], arrC[MAX];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arrA[i];
    for (int i = 0; i < n; i++) cin >> arrB[i];
    for (int i = 0; i < n; i++) cin >> arrC[i];

    sort(arrA, arrA + n);
    sort(arrB, arrB + n);
    sort(arrC, arrC + n);

    LL total = 0;
    for (int i = 0; i < n; i++) {
        // Đếm phần tử trong A nhỏ hơn arrB[i]
        LL countA = lower_bound(arrA, arrA + n, arrB[i]) - arrA;
        // Đếm phần tử trong C lớn hơn arrB[i]
        LL countC = n - (upper_bound(arrC, arrC + n, arrB[i]) - arrC);
        total += countA * countC;
    }
    cout << total;
}