```cpp // https://dashoj.com/d/lqbproblem/p/51 #include <bits/stdc++.h> #define N 100010 using namespace std; typedef long long ll; ll n, ans = 0; vector<ll> a(N), b(N), c(N); int main() { cin >> n; // 输入 for (ll i = 1; i <= n; i++) cin >> a[i]; for (ll i = 1; i <= n; i++) cin >> b[i]; for (ll i = 1; i <= n; i++) cin >> c[i]; sort(&a[1], &a[1] + n); // 排序 sort(&b[1], &b[1] + n); sort(&c[1], &c[1] + n); for (ll i = 1; i <= n; i++) { ll cnt, x = b[i], l = 1, r = n; while (l <= r) { ll m = (l + r) >> 1; if (a[m] < x) l = m + 1; else r = m - 1; } cnt = l - 1, l = 1, r = n; while (l <= r) { ll m = (l + r) >> 1; if (c[m] > x) r = m - 1; else l = m + 1; } ans += cnt * (n - r); } cout << ans << endl; return 0; } ```

二分 ``` #include <iostream> #include <algorithm> using namespace std; typedef long long ll; const int N = 1e5+100; int a[N],b[N],c[N]; int main(){ int n; cin >> n; for(int i =0;i<n;i++) cin >> a[i]; for(int i=0;i<n;i++) cin >> b[i]; for(int i =0;i<n;i++) cin >> c[i]; sort(a,a+n); sort(b,b+n); sort(c,c+n); ll ans =0; for(int i=0;i<n;i++){ ll x =lower_bound(a,a+n,b[i])-a; ll y =n-(upper_bound(c,c+n,b[i])-c); ans +=x*y; } cout << ans << endl; } ``` ll x = lower_bound(a,a+n,b[i])-a;: 这里使用lower_bound函数在排序后的数组a中找到第一个不小于b[i]的元素的位置。然后，从这个位置减去数组a的起始位置a，得到的x是数组a中小于b[i]的元素的数量。 ll y = n-(upper_bound(c,c+n,b[i])-c);: 这里使用upper_bound函数在排序后的数组c中找到第一个大于b[i]的元素的位置。从n减去这个位置与数组c起始位置的差，得到的y是数组c中大于b[i]的元素的数量。 ans += xy;: 最后，计算x和y的乘积，并累加到ans上。这个乘积实际上是对于每个b[i]，在a中小于它的元素数量与在c中大于它的元素数量的组合。

``` #include <bits/stdc++.h> #define endl '\n' using namespace std; typedef pair<int,int> aII; using ll = long long; using ULL = unsigned long long; const int N = 1e5+5; ll n; int a[N], b[N], c[N]; int finds(int x) { int l = 1, r = n; while (l < r) { int mid = (l + r + 1) >> 1; if (a[mid] < x) l = mid; else r = mid - 1; } if (a[l] < x) return l; else return 0; } int findb(int x) { int l = 1, r = n; while (l < r) { int mid = (l + r) >> 1; if (c[mid] > x) r = mid; else l = mid + 1; } if (c[r] > x) return n - r + 1; else return 0; } inline 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(b+1,b+1+n); sort(c+1,c+1+n); ll cnt = 0; for (int i = 1; i <= n; i++) { ll x = finds(b[i]); ll y = findb(b[i]); cnt += x * y; } cout << cnt << endl; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int _ = 1; //int _; cin >> _; while (_--) solve(); return 0; } ```

include typedef long long LL; using namespace std; const int N = 1e5 + 10; LL n,k; int a[N],b[N],c[N]; LL res; int cnt[N]; int main() { cin>>n; for(int i=1;i >a[i]; for(int j=1;j >b[j]; for(int i=1;i >c[i]; sort(a+1,a+n+1); sort(c+1,c+n+1); sort(b+1,b+n+1); ``` int numa=1,numc=1; for(int i=1;i<=n;i++) { while(numa<=n && a[numa]<b[i]) numa++; while(numc<=n && c[numc]<=b[i]) numc++; res+=(LL)(numa-1)*(n-numc+1); } cout<<res<<endl; return 0; ``` }

``` #include <iostream> #include <algorithm> using namespace std; const int N = 100010; int a[N], b[N], c[N]; long long n,p,num1,num2,idx,num; 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(b + 1, b + 1 + n); sort(c + 1, c + 1 + n); /* for (int i = 1; i <= n; i ++ ) cout << a[i] << " "; cout << endl; for (int i = 1; i <= n; i ++ ) cout << b[i] << " "; cout << endl; for (int i = 1; i <= n; i ++ ) cout << c[i] << " "; cout << endl; */ for (int i = 1; i <= n; i ++ ) { idx = 0; long long l = 1, r = n; while (l < r) { long long mid = l + r + 1 >> 1; if (a[mid] < b[i]) l = mid; else r = mid - 1; } num1 = l; //cout << num1 << " "; l = 1, r = n; while (l < r) { long long mid = l + r >> 1; if (c[mid] > b[i]) r = mid; else l = mid + 1; } num2 = l; //cout << num2 << endl; if (a[num1] < b[i] && c[num2] > b[i]) { idx =(num1 * (n - num2 + 1)); num += idx; } //cout << idx; } cout << num; return 0; } ```