#### 二分
*
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5+100;
int a[N],b[N],c[N];
int main(){
int n;
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 ans =0;
for(int i=0;i<n;i++){
ll x =lower_bound(a,a+n,b[i])-a;
ll y =n-(upper_bound(c,c+n,b[i])-c);
ans +=x*y;
}
cout << ans << endl;
}ll x = lower_bound(a,a+n,b[i])-a;: 这里使用lower_bound函数在排序后的数组a中找到第一个不小于b[i]的元素的位置。然后,从这个位置减去数组a的起始位置a,得到的x是数组a中小于b[i]的元素的数量。ll y = n-(upper_bound(c,c+n,b[i])-c);: 这里使用upper_bound函数在排序后的数组c中找到第一个大于b[i]的元素的位置。从n减去这个位置与数组c起始位置的差,得到的y是数组c中大于b[i]的元素的数量。*
ans += x*y;: 最后,计算x和y的乘积,并累加到ans上。这个乘积实际上是对于每个b[i],在a中小于它的元素数量与在c中大于它的元素数量的组合。
0 回复
0 转发
1 喜欢
2 阅读



