题目描述
blablabla
样例
blablabla
算法1
(二分) $O(nlogn)$
本题注意事项
1)二分找个数要用long long,否则会出错
2)a(i) < b(j) < c(k)
i. 找到a中比b(i)小的个数pos1
ii. 找到c中比b(i)大的个数pos2
最后结果就是 sum += pos1 * pos2;
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N], b[N], c[N];
int n;
//在a中找比b[i]小的个数
long long binary1(int q[], int k)
{
int l = 1, r = n;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(q[mid] < k) l = mid;
else r = mid - 1;
}
if(q[l] >= k) return 0;
return l;
}
//在c中找比b[i]大的个数
long long binary2(int q[], int k)
{
int l = 1, r = n;
while(l < r)
{
int mid = l + r >> 1;
if(q[mid] <= k) l = mid + 1;
else r = mid;
}
if(q[l] <= k) return 0;
return n - l + 1;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
for(int i = 1; i <= n; i++) scanf("%d", &c[i]);
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
sort(c + 1, c + n + 1);
//找
long long sum = 0;
for(int i = 1; i <= n; i++)
{
//在a中找比b[i]小的个数
long long pos1 = binary1(a, b[i]);
//在c中找比b[i]大的个数
long long pos2 = binary2(c, b[i]);
// printf("%d %d ", pos1, pos2);
sum += pos1 * pos2;
}
printf("%lld", sum);
return 0;
}