//思路:二分 先对三个数组进行sort排序,然后遍历b数组,对于b中的每一个数b[i],在a数组中寻找最后一个
//小于b[i]的数的下标,这里我们记做l.在再c数组中寻找第一个大于b[i]的数的下标,这里我们记做r
//可知a数组中,小于b[i]的数的个数为l+1,c数组中大于b[i]数的个数为n-r.(下标从0开始)
//因此在三元递增组中,以b[i]为中间数的个数为(l+1)*(n-r).
//遍历b数组,res+=(l+1)*(n-r) 即为答案
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], b[N], c[N];
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < n; i++) scanf("%d", &b[i]);
for (int i = 0; i < n; i++) scanf("%d", &c[i]);
sort(a, a + n); //二分需要满足单调性
sort(b, b + n);
sort(c, c + n);
LL res = 0; //答案可能会很大,会爆int
for (int i = 0; i < n; i++)
{
int l = 0, r = n - 1; //二分查找a数组中最后一个小于b[i]的数的下标
while (l < r)
{
int mid = (l + r + 1) / 2;
if (a[mid] < b[i]) l = mid;
else r = mid - 1;
}
if (a[l] >= b[i]) //如果未找到小于b[i]的数,将x标记为-1,后续计算时 x+1==0
{
l = -1;
}
int x = l;
l = 0, r = n - 1;
while (l < r)
{
int mid = (l + r) / 2;
if (c[mid] > b[i]) r = mid;
else l = mid + 1;
}
if (c[l] <= b[i]) //如果未找到大于b[i]的数,将y标记为n,后续计算时 n-y==0;
{
r = n;
}
int y = r;
res += (LL)(x + 1)*(n - y);
}
printf("%lld\n", res);
return 0;
}
orz,边界没处理清楚看了你的懂了
有点没看懂
# res += (LL)(x + 1)*(n - y);
希望大佬解释下QwQ
x+1是数组a中小于b【i】的数量,n—y是c中大于b【i】的数量,之后利用乘法定理就可以求出对应每一个b【i】,分别有多少种,之后再对每个b【i】求和即可
我懂了,谢谢!
为什么是x+1而不是x?
因为x是取的l的值,而l的下标是从0开始的。假如说二分完l处于a[0]位置,则说明a中还是有一个数小于b[j]的。
hhhh我的想法和你的一摸一样
如果i=0时。 int l = 0, r = n - 1;这个要怎么写呢
未找到大于或小于b[i]的数,可以在if语句中用continue跳过此次for循环了
(if (a[mid] < b[i]) l = mid;
else r = mid - 1;)
和
(if (c[mid] > b[i]) r = mid;
else l = mid + 1;)
处理的很好。
orz
感谢分享
写得好 我忘了处理小于大于b[i]的数
写的很清楚诶