solution.md

# 递增三元组

给定三个整数数组  
A = [A1, A2, ... AN],   
B = [B1, B2, ... BN],   
C = [C1, C2, ... CN]，  
请你统计有多少个三元组(i, j, k) 满足：
1. 1 <= i, j, k <= N  
2. Ai < Bj < Ck  

**输入格式**

第一行包含一个整数N。  
第二行包含N个整数A1, A2, ... AN。  
第三行包含N个整数B1, B2, ... BN。  
第四行包含N个整数C1, C2, ... CN。  

对于30%的数据，1 <= N <= 100    
对于60%的数据，1 <= N <= 1000   
对于100%的数据，1 <= N <= 100000 0 <= Ai, Bi, Ci <= 100000   

**输出格式**

一个整数表示答案

**样例输入**

```
3
1 1 1
2 2 2
3 3 3
```
**样例输出**

```
27
```

以下<span style="color:red">错误</span>的一项是？

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after

```cpp

```

## 答案

```cpp
int main()
{
    int n;
    long long ans = 0;
    cin >> n;
    int I[n], J[n], K[n];
    for (int i = 0; i < n; i++)
    {
        cin >> I[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> J[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> K[i];
    }
    sort(I, I + n);
    sort(J, J + n);
    sort(K, K + n);
    int index_min_i = 0, index_min_j = 0;
    for (int i = 0; i < n; i++)
    {
        int count1 = 0, count2 = 0;
        for (int j = index_min_i; j < n; j++)
        {
            if (I[i] < J[j])
            {
                index_min_i = j;
                count1 = n - j;
                for (int k = index_min_j; k < n; k++)
                {

                    count2 = n - k;
                    index_min_j = k;
                    ans += (long long)(count1 * count2);
                }
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}
```
## 选项


### A

```cpp
const int maxn = 1e5 + 10;
typedef long long ll;
int a[maxn];
int b[maxn];
int c[maxn];
int main()
{
    int n;
    ll ans = 0;
    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 cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < n; i++)
    {
        while (cnt1 < n && a[cnt1] < b[i])
            cnt1++;
        while (cnt2 < n && c[cnt2] <= b[i])
            cnt2++;
        ans += cnt1 * (n - cnt2);
    }

    cout << ans << endl;
}
```

### B

```cpp
#define ll long long
using namespace std;

const int N = 100000 + 10;

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

int find2(int x, int y[])
{
    int l = 1, r = n;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (y[mid] > x)
            r = mid;
        else
            l = mid + 1;
    }
    if (y[r] <= x)
        return 0;
    return n - r + 1;
}

int find1(int x, int y[])
{
    int l = 1, r = n;
    while (l < r)
    {
        int mid = (l + r + 1) >> 1;
        if (y[mid] < x)
            l = mid;
        else
            r = mid - 1;
    }
    if (y[l] >= x)
        return 0;
    return l;
}

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);
    long long ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int x = find1(b[i], a);
        int y = find2(b[i], c);

        ans += 1ll * x * y;
    }
    cout << ans;
    return 0;
}
```

### C

```cpp
typedef long long LL;

const int N = 1e5 + 10;
int a[N], b[N], c[N], sa[N], sc[N], s[N]; 

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

    for (int i = 0; i < n; i++)
        s[a[i]]++; 
    for (int i = 1; i < N; i++)
        s[i] += s[i - 1]; 
    for (int i = 0; i < n; i++)
        sa[i] = s[b[i] - 1]; 

    memset(s, 0, sizeof s);

    for (int i = 0; i < n; i++)
        s[c[i]]++;
    for (int i = 1; i < N; i++)
        s[i] += s[i - 1];
    for (int i = 0; i < n; i++)
        sc[i] = s[N - 1] - s[b[i]]; 

    LL res = 0;
    for (int i = 0; i <= n; i++)
        res += (LL)sa[i] * sc[i];
    cout << res;
}
```