AcWing 1236. 递增三元组
原题链接
中等
作者:
Donx
,
2021-02-02 19:28:15
,
所有人可见
,
阅读 314
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N],b[N],c[N],n;
typedef long long LL;
LL res;
int xyb(int x) {//返回>=x的第一个位置
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if(a[mid] < x) l = mid+1;
else r = mid;
}
if(a[l] >= x) return l;
else return n;//a中的数都小于x
}
int dyb(int x) {// 返回<=x的最后一个位置
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r + 1>>1;
if(c[mid] > x) r = mid-1;
else l = mid;
}
if(c[l] <= x) return n-1-l;
else return n;// c里面的数都大于x
}
int main () {
cin>>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(c,c+n);
for(int i=0; i<n; i++) {
int x = b[i];
res += (LL) dyb(x) * xyb(x);
}
cout<<res;
return 0;
}