题目:给定三个数组,从每个数组中选择一个数,求出严格单调的3个数的总组合数
前缀和:
思路:看一下每个数的大小为10w,我们可以通过前缀和来做,
通过前缀和记录每个数大于等于该数的总数;因为我们要求严格单调上升的序列,所以只要利用乘法原则即可求出小于/大于当前值的所有数的数量(因为每个数都小于等于10w,才可以用前缀和,若为10^9,我们只能通过双指针或二分来做)
前缀和时间复杂度:O(n);
二分:
思路:对于每一个数,我们可以通过二分来找到第一个大于该数/小于该数的下标,再通过乘法原理也能求出所有组合
二分时间复杂度:O(nlogn)
前缀和:
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 100010;
int n;
ll a[N];
ll b[N];
ll c[N];
ll suma[N],sumb[N],sumc[N];
int main()
{
cin >> n;
for (int i = 1; i <= n ; i ++) scanf("%lld",&a[i]),suma[a[i]] ++;
for (int i = 1; i <= n ; i ++) scanf("%lld",&b[i]),sumb[b[i]] ++;
for (int i = 1; i <= n ; i ++) scanf("%lld",&c[i]),sumc[c[i]] ++;
for (int i = 1; i <= N ; i ++)
{
suma[i] += suma[i - 1];
sumb[i] += sumb[i - 1];
sumc[i] += sumc[i - 1];
}
ll ans = 0;
for (int i = 1 ; i <= n; i ++)
{
ans += suma[b[i] - 1] * (sumc[N] - sumc[b[i]]);
}
cout << ans << endl;
return 0;
}
二分:
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 100010;
ll n;
ll g[3][N];
int main()
{
cin >> n;
for (int i = 0; i < 3; i ++)
{
for(int j = 0; j < n ; j ++)
{
scanf("%lld",&g[i][j]);
}
}
for (int i = 0; i < 3 ; i ++) sort(g[i],g[i] + n);
ll ans = 0;
for (int i = 0 ; i < n ; i ++)
{
int l = 0, r = n - 1;
while (l < r)
{
int m = l + r + 1 >> 1;
if (g[0][m] < g[1][i]) l = m;
else r = m - 1;
}
if (g[0][l] >= g[1][i]) l = -1;
ll p1 = l;
l = 0, r = n - 1;
while (l < r)
{
int m = l + r >> 1;
if (g[2][m] <= g[1][i]) l = m + 1;
else r = m;
}
if (g[2][l] <= g[1][i]) l = n;
ll p2 = l;
ans += (p1 + 1) * (n - p2);
}
cout << ans << endl;
return 0;
}