二分模板题

题目传送门

主要思路：

• 暴力会tle n的3次方了
• 然后 二分可以找中间然后去二分枚举两边
  最后结果 ans+=a小于它的数*c大于它的数 注意要判断是否符合条件 即如果a的小于它的数还大于它就不成立 或者c的数小于它也不成立
• 结果 要注意转long long ans+=(long long)tp1*tp2; int->longlong

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100009],b[100009],c[100009];
//找到第一个大于该数字的数
int get_max(int *num,int x){
   int l=1;int r=n; int mid=0;
   while(l<r){
       mid=(l+r)/2;
       if(num[mid]>x) r=mid;
       else l=mid+1;
   }
   return l;
}
// 得到第一个小于它的数
int get_min(int *num,int x)
{
   int l=1;
   int r=n; 
   int mid=0;
   while(l<r){
       mid=(l+r+1)/2;
       if(num[mid]<x) l=mid;
       else r=mid-1;
   }
   return l;
}
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+1,a+1+n);
       sort(c+1,c+1+n);
     long long ans=0;
       for(int i=1;i<=n;i++){
           // cout<<get_max(c,b[i])<<endl;
           // cout<<get_min(a,b[i])<<endl;
           // if(b[i]<=a[1]||b[i]>=c[n]) continue;
           int tp1=n-get_max(c,b[i])+1;
           int tp2=get_min(a,b[i]);
           if(c[get_max(c,b[i])]<=b[i]||a[get_min(a,b[i])]>=b[i]) continue;
           ans+=(long long)tp1*tp2;
       }
       cout<<ans<<endl;
       return 0;
}
// #include <iostream>
// #include <cstdio>
// #include <algorithm>
// using namespace std;

// typedef long long LL;
// const int N = 1e5+10;
// int num[3][N];

// int main() {
//     int n;
//     scanf("%d", &n);
//     for(int i = 0; i < 3; ++i) 
//         for(int j = 1; j <= n; ++j) 
//             scanf("%d", &num[i][j]);
//     // for(int i = 0; i < 3; ++i)
//         sort(num[0]+1, num[0]+n+1);
//         sort(num[2]+1, num[2]+n+1);
//     LL ans = 0;
//     //枚举B，寻找A满足的个数以及C满足的个数相乘
//     for(int i = 1; i <= n; ++i) {
//         int key = num[1][i];
//         //A中二分查找第一个小于key的数的下标
//         int pos1 = lower_bound(num[0]+1, num[0]+n+1, key)-num[0]-1;
//         //C中二分查找第一个大于key的数的下标
//         int pos2 = upper_bound(num[2]+1, num[2]+n+1, key)-num[2];
//         if(pos1 >= 1 && pos2 <= n) {
//             ans += (LL)pos1*(n-pos2+1);
//         }
//     }
//     cout<<ans<<endl;
//     return 0;
// }