题目链接:递增三元组 - 洛谷 P8667 - Virtual Judge (vjudge.net)
解题思路:该题让统计 (ai<bi<ci) 这种三元组的数量,数据量是1e5很显然得使用至少为 nlogn 的时间复杂度的算法才可以通过,因为题目要求 ai<bi 并且 bi<ci 所以可以通过枚举 bi 来进行三元组的查找,那么怎么样可以快速的统计数量呢,可以将数组 a、c 进行排序,然后通过二分来找到第一小于 bi 的 ai,和第一个大于 bi 的 ci 的下标,然后直接求和就好
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100010
ll n;
ll A[N],B[N],C[N];
map<ll,ll> a,b,c;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
ll u;
cin>>u;
a[u]++;
A[i]=u;
}
for(int i=1;i<=n;i++){
ll u;
cin>>u;
b[u]++;
B[i]=u;
}
for(int i=1;i<=n;i++){
ll u;
cin>>u;
c[u]++;
C[i]=u;
}
sort(A+1,A+n+1);
sort(C+1,C+n+1);
ll ans=0;
ll mid;
for(auto [bi,bj]:b){
ll l=1,r=n;
while(l<=r){
mid=l+r>>1;
if(C[mid]<=bi)l=mid+1;
else r=mid-1;
}
ll ll=1,rr=n;
while(ll<=rr){
mid=ll+rr>>1;
if(A[mid]>=bi)rr=mid-1;
else ll=mid+1;
}
if(bi>A[rr-1]&&C[l]>bi)ans+=rr*bj*(n-r);
}
cout<<ans<<endl;
return 0;
}