AcWing:1236. 递增三元组

给定三个整数数组

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。

输出格式

一个整数表示答案。

数据范围

1≤N≤10^5
0≤Ai,Bi,Ci≤10^5

输入样例：

3
1 1 1
2 2 2
3 3 3

输出样例：

27

 思路过程:

        要想知道a>b>c的排列方法有多少种,可以关注到b这个变量很关键,起到了承上启下的作用,我可以固定b,将符合条件的a,c有多少种求出,最后相乘即可得出方案数

        1.先排序

        2.二分查找

 AC代码:

#include <bits/stdc++.h>using namespace std;typedef long long LL;
const int N = 1e5 + 10;
int n;
int a[N] , b[N] , c[N];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);LL ans = 0;/* 核心 *//* 以b为中间值,进行与a,c比较,将两者数量相乘*/for(int i = 1; i <= n ; i ++){int key = b[i];int pos1 = lower_bound(a + 1, a + n + 1, key) - a - 1;int pos2 = upper_bound(c + 1, c + n + 1, key) - c;if(pos1 >= 1 && pos2 <= n) ans += (LL)pos1 * (n - pos2 + 1);}cout << ans << endl;return 0;
}