(二分做法)递增三元组
二分加前缀和
大问题拆成小问题
因为本质是从三个数组里面各挑一个下标,所以排序并不会影响结果
不妨对a b c三个数组进行排序。
如果我们只考虑两个数组b,c,很容易想到二分,确定一个c,找到最后一个小于它的b,时间复杂度$O(nlogn)$
但是c与b之间用一次二分,b与a之间还用一次二分,就会变成$(n^2log^2n)$,n是1e5,肯定不行,那有没有什么办法确定c的值后,用$O(1)$的时间复杂度得到a与b的所有可能值
方法就是提前预处理一遍,当前b和在它前面的所有b一共可以选择多少个a,对于一个b,用二分就能得到它可以选多少a,再用前缀和就能得到当前b和在它前面的所有能选择的a的组合的个数了
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int a[N],b[N],c[N];
long long s[N];
int n;
long long ans;
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,a+n+1);
sort(b,b+n+1);
sort(c,c+n+1);
for(int i = 1;i<=n;i++)
{
int x = b[i];
int l = 1,r = n;
while(l<r)
{
int mid = l+r>>1;
if(a[mid]>=x)r = mid;
else l = mid+1;
}
if(a[l]<b[i])s[i] = (l) + s[i-1];
else s[i] = (l-1) + s[i-1];
}
// for(int i = 0;i<=n;i++)cout<<s[i]<<' ';
// cout<<endl;
for(int i = 1;i<=n;i++)
{
int x = c[i];
int l = 1,r = n;
while(l<r)
{
int mid = l+r>>1;
if(b[mid]>=x)r = mid;
else l = mid+1;
}
if(b[l]<c[i])ans+=s[l];
else ans+=s[l-1];
}
cout<<ans<<endl;
}