题目描述

给定三个整数数组
A=[A1,A2,…AN],
B=[B1,B2,…BN],
C=[C1,C2,…CN],
请你统计有多少个三元组 (i,j,k)
满足：
1≤i,j,k≤N
Ai<Bj<Ck

输入格式
第一行包含一个整数 N。
第二行包含 N个整数 A1,A2,…AN。
第三行包含 N个整数 B1,B2,…BN。
第四行包含 N个整数 C1,C2,…CN。
输出格式
一个整数表示答案。

数据范围
1≤N≤105,
0≤Ai,Bi,Ci≤105

样例

输入样例：
3
1 1 1
2 2 2
3 3 3

输出样例：
27

//二分
遍历B[]中的每个数字，用A[]数组小于B[i]的数字总个数乘上C[]数组中大于B[i]的数字总个数。
首先将A[]，C[]数组分别排序，然后用二分逐个查找B[]中的元素，
在A[]数组中查找小于B[i]的最大下标，如果可以找到则 下标+1表示A[]数组中小于B[i]的个数 cnt=l+1或者r+1，如果找不到(A[l]>=B[i]),则A[]数组中小于B[i]的个数等于0
在C[]数组中查找大于B[i]的最小下标，如果可以找到则 C[]中元素个数 - 下标表示C[]数组中小于B[i]的个数 cnt=n - l或者n - r，如果找不到(A[l]<=B[i]),则A[]数组中小于B[i]的个数等于0

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 int n,cnt,ct;
 int a[100005],b[100005],c[100005];
int main(int argc, char** argv) {
  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);//对a,c数组，b数组排序不排序无所谓
sort(c,c+n);
long long res=0;
for(int i=0;i<n;i++){
    int l=0,r=n-1;
  while(l<r){   //在A[]数组中查找小于B[i]的最大下标
    int mid=(l+r+1)/2;
    if(a[mid]<b[i]) l=mid;
    else r=mid-1;
  }        
  cnt=l+1;
  if(a[l]>=b[i]) cnt=0;
  l=0,r=n-1;  //不要忘了，重置回来
   while(l<r){ //在C[]数组中查找大于B[i]的最小下标，
    int mid=(l+r)/2;
    if(c[mid]>b[i]) r=mid;
    else l=mid+1;
  }
    ct=n-l; 
    if(c[l]<=b[i]) ct=0;
  res+=1ll*ct*cnt;
}
cout<<res<<endl;
    return 0;
}

//前缀和
首先用数组cnta[],cntb[]分别统计出A[]数组，C[]数组中每个数字出现的次数，求出再根据统计数字个数的数组cnta[],cntb[],求出前缀和数组sa[],sc[],然后遍历B[]中的每个数字，用A[]数组小于B[i]的数字总个数乘上C[]数组中大于B[i]的数字总个数。
扩展：
求一个原数组a[]第l个元素到第r个元素的和，其实就是它的前缀和数组s[]中用 s[r]-s[l-1]。

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std; 
int A[10005],B[100005],C[100005],cnta[100005],cntc[100005];
int sa[100005],sc[100005];
int n;
int main(int argc, char** argv) {
scanf("%d",&n);
for(int i=0;i<n;i++){
    scanf("%d",&A[i]);
    cnta[A[i]]++;
}   
sa[0]=cnta[0];//防止数组越界 
for(int i=1;i<=100005;i++){
    sa[i]=sa[i-1]+cnta[i];
}
for(int i=0;i<n;i++){
    scanf("%d",&B[i]);
}   
for(int i=0;i<n;i++){
    scanf("%d",&C[i]);
    cntc[C[i]]++;
}   
sort(C,C+n);
sc[0]=cntc[0]; //以防数组-1越界 
for(int i=1;i<=100005;i++){  
 //这里循环条件不可以sort(C,C+n);i<C[n-1]因为i这取决于B[]的大小，B[]数组的范围最大是1e5，
 //如果写成C[n-1]，sc[100005]会是0，其实应该为sc[C[n-1]],没有出现过的数字，cnt[]默认为0， 
    sc[i]=sc[i-1]+cntc[i];
}
long long res=0;
for(int i=0;i<n;i++){
    res+=1ll*sa[B[i]-1]*(sc[100005]-sc[B[i]]);
} 
printf("%lld\n",res);
    return 0;
}