二分模板题

题目传送门

主要思路：

• 暴力会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;
// }