AcWing 1236. 递增三元组
原题链接
中等
作者:
季之秋
,
2021-03-03 17:38:51
,
所有人可见
,
阅读 218
二分
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int N=100010;
int n=sc.nextInt();
int a[]=new int[n];
int b[]=new int[n];
int c[]=new int[n];
for(int i=0;i<n;i++) a[i]=sc.nextInt();
for(int i=0;i<n;i++) b[i]=sc.nextInt();
for(int i=0;i<n;i++) c[i]=sc.nextInt();
Arrays.sort(a);
Arrays.sort(c);
long res=0;
for(int i=0;i<n;i++){
int little=0;
int big=0;
int l=0,r=n-1;
while(l<r){
int mid=(l+r)/2;
if(a[mid]>=b[i]) r=mid; //a中小于b的最大数下标
else l=mid+1;
}
if(a[l]>=b[i]) little=l; //可能找不到大于等于b[i]的数
else little=l+1;
l=0;r=n-1;
while(l<r){
int mid=(l+r+1)/2;
if(c[mid]<=b[i]) l=mid; //c中大于b的最小数下标
else r=mid-1;
}
if(c[r]<=b[i]) big=n-1-r; //可能找不到小于等于b[i]的数
else big=n-r;
res+=(long)little*big;
}
System.out.println(res);
}
}
打表哈希表 + 前缀和
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int N=100010;
int n=sc.nextInt();
int a[]=new int[n];
int b[]=new int[n];
int c[]=new int[n];
int s[]=new int[N];
int cnt[]=new int[N];
int as[]=new int[N];
int cs[]=new int[N];
for(int i=0;i<n;i++) a[i]=sc.nextInt()+1;
for(int i=0;i<n;i++) b[i]=sc.nextInt()+1;
for(int i=0;i<n;i++) c[i]=sc.nextInt()+1;
for(int i=0;i<n;i++) cnt[a[i]]++;
for(int i=1;i<N;i++) s[i]=s[i-1]+cnt[i];
for(int i=0;i<n;i++) as[i]=s[b[i]-1];
Arrays.fill(s,0);
Arrays.fill(cnt,0);
for(int i=0;i<n;i++) cnt[c[i]]++;
for(int i=1;i<N;i++) s[i]=s[i-1]+cnt[i];
for(int i=0;i<n;i++) cs[i]=s[N-1]-s[b[i]];
long res=0;
for(int i=0;i<n;i++) res+=(as[i]*(long)cs[i]);
System.out.println(res);
}
}