AcWing 1236. 递增三元组
原题链接
中等
作者:
tire
,
2025-04-10 19:49:59
· 山西
,
所有人可见
,
阅读 2
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+10;
const int mod = 100003;
int n,m;
int qmi(int a,int k){
int res = 1;
while(k){
if(k&1) res = res * a % mod;
a = a * a % mod;
k >>= 1;
}
return res;
}
int a[N],b[N],c[N];
void solve(){
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);
int res = 0;
for(int i = 1;i<=n;i++){
int x = b[i];
int l = 0,r = n;
while(l < r){
int mid = (l + r + 1) >> 1;
if(a[mid]<x) l = mid;
else r = mid - 1;
}
int cnta = l;
l = 1,r = n + 1;
while(l < r){
int mid = (l + r) >> 1;
if(c[mid]>x) r = mid;
else l = mid + 1;
}
int cntb = 0;
if(l != n + 1) cntb = n - l + 1;
res += cnta * cntb;
}
cout << res << '\n';
}
signed main(){
int _ = 1;
while(_--){
solve();
}
return 0;
}