题目分析
首先考虑暴力做法，三个数组嵌套枚举，O(n3)的时间复杂度，n≤105一定会超时。
尝试通过枚举的次序进行优化本题，先枚举B数组，在A中寻找小于B[i]的数的个数cnt1，在C中寻找大于B[i]的数的个数cnt2，带有B[i]的合法选择数就是cnt1*cnt2。
用暴力查找时间总的时间复杂度为O(n2)，还是会超时。
二分
既然是查找，那么可以考虑进行二分查找，查找前先通过排序预处理三个数组，排序时间复杂度O(nlog2n),枚举B的所有元素+查找A,C中的元素时间复杂度也是O(nlog2n)，总的时间复杂度降为O(nlog2n)
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
int num[3][N];
int main() {
int n;
scanf("%d", &n);
for(int i = 0; i < 3; ++i)
for(int j = 1; j <= n; ++j)
scanf("%d", &num[i][j]);
for(int i = 0; i < 3; ++i)
sort(num[i]+1, num[i]+n+1);
LL ans = 0;
//枚举B，寻找A满足的个数以及C满足的个数相乘
for(int i = 1; i <= n; ++i) {
int key = num[1][i];
//A中二分查找第一个小于key的数的下标
int pos1 = lower_bound(num[0]+1, num[0]+n+1, key)-num[0]-1;
//C中二分查找第一个大于key的数的下标
int pos2 = upper_bound(num[2]+1, num[2]+n+1, key)-num[2];
if(pos1 >= 1 && pos2 <= n) {
ans += (LL)pos1*(n-pos2+1);
}
}
cout<<ans<<endl;
return 0;
}
双指针
进一步对查找进行优化，对于排过序的数组A和B，寻找A中小于B[i]的元素的个数可以考虑双指针算法，因为每个指针最多移动n次，故查找的时间复杂度降到O(n)，查找C与查找A同理，只是找第一个大于B的位置。
只需要将上述二分程序中的
//二分
for(int i = 1; i <= n; ++i) {
int key = num[1][i];
//A中二分查找第一个小于key的数的下标
int pos1 = lower_bound(num[0]+1, num[0]+n+1, key)-num[0]-1;
//C中二分查找第一个大于key的数的下标
int pos2 = upper_bound(num[2]+1, num[2]+n+1, key)-num[2];
if(pos1 >= 1 && pos2 <= n) {
ans += (LL)pos1*(n-pos2+1);
}
}
更改为
//双指针
int a = 1, c = 1;
for(int i = 1; i <= n; ++i) {
int key = num[1][i];
while(a<=n && num[0][a] < key) a++;
while(c<=n && num[2][c] <= key) c++;
ans += (LL)(a-1)*(n-c+1);
}
完整的双指针程序为：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
int num[3][N];
int main() {
int n;
scanf("%d", &n);
for(int i = 0; i < 3; ++i)
for(int j = 1; j <= n; ++j)
scanf("%d", &num[i][j]);
for(int i = 0; i < 3; ++i)
sort(num[i]+1, num[i]+n+1);
LL ans = 0;
//枚举B，寻找A满足的个数以及C满足的个数相乘
int a = 1, c = 1;
for(int i = 1; i <= n; ++i) {
int key = num[1][i];
while(a<=n && num[0][a] < key) a++;
while(c<=n && num[2][c] <= key) c++;
ans += (LL)(a-1)*(n-c+1);
}
cout<<ans<<endl;
return 0;
}
前缀和
之前的双指针算法时间复杂度的瓶颈为：排序O(nlog2n)
考虑是否可以不排序在O(n)的时间内解决此问题呢？
既然要排序实现快速的查找A中小于B[i]的数的个数，可以将数组A中所有元素出现的次数存入一个哈希表中，因为数组中元素的范围只有n5, 可以开一个大的数组cnta 作为哈希表。
在枚举B中元素时，我们需要快速查找找小于B[i]的所有元素的总数，只需要在枚举之前先将求出表中各数的前缀和即可。
查找C与查找A同理可得。
C++代码实现
//前缀和
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
int A[N], B[N], C[N];
int cnta[N], cntc[N], sa[N], sc[N];
int main() {
int n;
scanf("%d", &n);
//获取数i在A中有cntc[i]个，并对cnt求前缀和sa
for(int i = 1; i <= n; ++i) {
scanf("%d", &A[i]);
cnta[++A[i]]++;
}
sa[0] = cnta[0];
for(int i = 1; i < N; ++i) sa[i] = sa[i-1]+cnta[i];
//B只读取即可
for(int i = 1; i <= n; ++i) scanf("%d", &B[i]), B[i]++;
//获取数i在C中有cntc[i]个，并对cnt求前缀和sc
for(int i = 1; i <= n; ++i) {
scanf("%d", &C[i]);
cntc[++C[i]]++;
}
sc[0] = cntc[0];
for(int i = 1; i < N; ++i) sc[i] = sc[i-1]+cntc[i];
//遍历B求解
LL ans = 0;
for(int i = 1; i <= n; ++i) {
int b = B[i];
ans += (LL)sa[b-1] * (sc[N-1] - sc[b]);
}
cout<<ans<<endl;
return 0;
}
运行时间
二分：725 ms
双指针：454 ms
前缀和：179 ms
一直以为lower_bound是找大于key的第一个位置，upper_bound是找小于key的第一个值，测了半天都有错😭
lower_bound( begin,end,num)：返回第一个大于等于参数key的迭代器 减一后变为第一个小于key的位置
upper_bound( begin,end,num)：返回第一个大于参数key的迭代器
一个是大于或等于 和 一个是大于
是滴，其实lower 和 upper 分别对应 大于等于、大于 还挺形象滴，
是不是应该是lower_bound( begin,end,num)：…… 减一后变为 最后一个 小于key的位置？
#include[HTML_REMOVED]
#include[HTML_REMOVED]
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++){ //此时我们的数字为a【i】 int key = b[i]; int l = lower_bound(a,a+n,key) - a - 1; int r = upper_bound(c,c+n,key) - c; if(l>=-1 && r <n){ res += (l+1)*(n-r); } // cout<<"l="<<l<<endl; // cout<<"r="<<r<<endl; // cout<<"res="<<res<<endl; // cout<<" "<<endl; } printf("%lld\n", res); return 0;}
佬能不能帮我看看为什么答案错误
我也感觉是最后一个小于key的位置…
是这样的
### 谢谢大佬，orz
前缀和这个好难看懂啊
tql
我的AC不了，能帮看一下吗
#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;
const int N=1e5+10;
int a[N],b[N],c[N];
int n;
typedef long long LL;
LL ans=0;
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+1+n); sort(b+1,b+1+n); for(int i=1;i<=n;i++) { //找出a<b int l=1,r=n; while(l<r) { int mid=(LL)l+r+1>>1; if(a[mid]<b[i]) l=mid; else r=mid-1; } LL temp_a; if(a[l]<b[i]) temp_a=l; else temp_a=0; //找出b>c l=1,r=n; while(l<r) { int mid=(LL)l+r>>1; if(c[mid]>b[i]) r=mid; else l=mid+1; } LL temp_c; if(c[l]>b[i]) temp_c=n-l+1; else temp_c=0; ans+=temp_a*temp_c; } cout<<ans<<endl; return 0;}
找到问题了，排序数组那里不小心写错了，本来是打算给c排序的结果把b给排序了
为什么双指针算法不会超时。如果n个数据，三组，第一层循环n，内层的while循环最坏是2n，那复杂度不也是你n^2吗，难道不会超时吗
排序之后因为元素在不断递增，只会走一轮，也就是O(n)了。
因为while中的a,c每一次都不是从1~n循环，而是不断累加
把指针放循环外定义就行了
这个嵌套循环不能用乘法原理，是加法原理
//A中二分查找第一个小于key的数的下标
int pos1 = lower_bound(num[0]+1, num[0]+n+1, key)-num[0]-1;
//C中二分查找第一个大于key的数的下标
int pos2 = upper_bound(num[2]+1, num[2]+n+1, key)-num[2];
为什么找大于不用-1呢？
-num[0]和-num[2]是什么意思啊
因为数组地址是连续的，这两个函数返回的是一个地址，这个地址减去首地址就是下标了
因为lower_bound()返回的是第一个不小于key的地址，然后我们要的是小于key的个数，所以要减一；upper_bound()返回的是第一个大于key的地址，我们找的也是大于key的，所以不用减一
orz
二分函数蓝桥杯给不给用啊
给的，支持到C++11
大佬爱你，我要扯你裤子
不愧是小新
tql
请问为什么统计a中某个数的个数是cnta[A[i]]; 而不是cnta[A[i]]++;
它不是用的是哈希吗？
有哪位大佬帮我看一下前缀和为啥过不了最后一个数据，边界问题好难搞
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;
const int N=100010;
int n,a[N],b[N],c[N];
int num[N],s[N];
int as[N],cs[N];
int main(){
cin>>n;
for(int i=1;i<=n;i)cin>>a[i];
for(int j=1;j<=n;j) {cin>>b[j];};
for(int k=1;k<=n;k) cin>>c[k];
//处理as
for(int i=1;i<=n;i) num[a[i]];//记录a[i]出现的次数
for(int i=1;i<=N;i) s[i]=s[i-1]+num[i]; //递推求得关于a[i]的所有前缀和
for(int i=1;i<=n;i) as[i]=s[b[i]-1]; //as代表比b[i]小的数的前缀和
memset(num,0,sizeof num);
memset(s,0,sizeof s);
//处理cs
for(int i=1;i<=n;i) num[c[i]];//记录c[i]出现的次数
for(int i=1;i<=N;i) s[i]=s[i-1]+num[i];//递推求得关于c[i]的所有前缀和
for(int i=1;i<=n;i) cs[i]=s[N-1]-s[b[i]];//cs代表比b[i]大的数的前缀和
//求结果
long long res=0;
for(int i=1;i<=n;i) {
res+=(long long)as[i]*cs[i];
}
cout<<res;
return 0;
}
ans += (LL)sa[b-1] * (sc[N-1] - sc[b]);
大佬， 请问这是什么意思？
因为只要在a数组找小于b[i]的所有数，a数组所有数的出现次数都在cnta里，求个前缀和就意味着，sa[i]代表小于等于i的所有数的出现次数，（数组a下表是有序的嘛）
b[i]又是整数，于是要找小于b[i]的，那不就是sa[b[i]-1]了吗。b[i]是整数
另一个同理，然后乘起来就好。（排列组合）
为什么求前缀和循环到N而不是n啊，这不会溢出么
n是每个数组的整数个数，而N是最大的数，就比如n = 3时，A[3] = {4,6,9}，由于存储的语句是cnta[A[ i ] ] ；用n作为截止点就不对了，你自己找个数代代就知道了
orz
orz是什么意思呀
膜拜大佬
看起来像一个小人跪着
#include[HTML_REMOVED]
using namespace std;
const int N = 1e5+10;
typedef long long ll;
int a[N],b[N],c[N],n;
ll binary_a(int x)
{
int l=0,r=n-1;
while(l[HTML_REMOVED]>1;
if(a[mid]<x)l=mid;
else r=mid-1;
}
return (ll)l;
}
ll binary_c(int x)
{
int l=0,r=n-1;
while(l[HTML_REMOVED]>1;
if(c[mid]>x)r=mid;
else l=mid+1;
}
return (ll)l;
}
int main()
{
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 res=0; for(int i=0;i<n;i++) { ll l = binary_a(b[i]);//最后一个小于b[i]的数 //cout<<"l="<<l<<" "; ll r = binary_c(b[i]);//第一个大于b[i]的数 //cout<<"r="<<r<<" "; if(a[l]<b[i]&&b[i]<c[r])res+=(l+1)*(n-r); } cout<<res; return 0;}
orz
orz
orz