做题的第一件事就是看范围。
注意到范围，想到应该要使用 \(O(n\times \log n)\) 的办法。
进而联想到排序与二分。
事实证明的确要使用排序与二分。
不说废话，我的思路是读入时顺便给三个数组排序，当然是从小到大。
然后，我们枚举第二个数组。
为什么枚举第二个呢？
因为它和另外两个都有直接的大小关系，可以帮助我们卡范围！
利用算法库自带的二分函数，来算出上中与中下的范围。
再利用加乘原理即可。
送上满分代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#define N (int)(1e5 + 5)
using namespace std;
int n, a[N], b[N], c[N];
void QwQ(int x[]) //作用：读入并排序。
{
for (int i = 1; i <= n; i++) scanf("%d", &x[i]);
sort(x+1, x+n+1);
}
int main()
{
//以下四行读入。
scanf("%d", &n);
QwQ(a);
QwQ(b);
QwQ(c);
//下面就是重点代码，注意 sum 的所使用的数据范围。
long long sum = 0;
for (int i = 1; i <= n; i++)
{
long long cntA = lower_bound(a+1, a+n+1, b[i]) - a - 1;
long long cntC = upper_bound(c+1, c+n+1, b[i]) - c - 1;
cntC = n - cntC; //上面的得出的是起始位置，还要卡范围。
sum += (cntA * cntC); //加乘原理。
}
printf("%lld", sum);
return 0;
}
2022-02-04 21:46:43
标签：二分,include,int,题解,读入,排序,AT3620 From： https://www.cnblogs.com/liangbowen/p/16622797.html