题目描述

给定三个整数数组

A=[A1,A2,…AN],
B=[B1,B2,…BN],
C=[C1,C2,…CN],

请你统计有多少个三元组 (i,j,k) 满足：

1≤i,j,k≤N
Ai<Bj<Ck
输入格式
第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,…AN。

第三行包含 N 个整数 B1,B2,…BN。

第四行包含 N 个整数 C1,C2,…CN。

输出格式
一个整数表示答案。

数据范围
1≤N≤10^5,
0≤Ai,Bi,Ci≤10^5

样例

输入样例：
3
1 1 1
2 2 2
3 3 3
输出样例：
27

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    const int N = 100000;
    int n, in[3][N+1], sign[N+1] = {0};
    long long int ans = 0, t1 = 0;

    cin >>n;
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < n; j++) cin >>in[i][j];

    sort(in[0], in[0]+n);
    sort(in[1], in[1]+n);
    sort(in[2], in[2]+n);

    int one = 0, two = 0, three = 0;
    while(two < n){
        if(one < n && in[0][one] < in[1][two]){
            t1++;
            one++;
        }else{
            sign[two] = t1;
            two++;
        }
    }

    two = 0, t1 = 0;
    while(three < n){
        if(two < n && in[1][two] < in[2][three]){
            t1 += sign[two];
            two++;
        }else{
            ans += t1;
            three++;
        }
    }
    cout <<ans;
    return 0;
}