自动搬运

查看原文

来自洛谷，原作者为

	liruixiong0101 当我们身陷无尽黑暗，不妨努力绽放光亮，搏一搏，让别人看到我们身上的微光，这是给予彼此的希望。

搬运于2025-08-24 22:41:15，当前版本为作者最后更新于2023-04-26 14:11:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P-1 前言：

双倍经验：[ABC077C] Snuke Festival。

P0 前置知识：

二分。

P1 题意：

给定三个长度为 $n$ 的整数数组 $a,b,c$。
请你统计有多少个三元组 $(i,j,k)$ 满足：

1. $1\le i,j,k\le n$
2. $a_i < b_j < c_k$

P3 思路：

首先想到的就是暴力，三层循环枚举。
时间复杂度：$O(n^3)$，分数：60pts，不可过。
暴力应该人人都会写，就不提供代码了。

暴力过不了就想优化。
我们枚举了前两层循环 $i,j$，若 $a_i<b_j$ 那么就不必再枚举所有的 $k$ 只需要所有大于 $b_j$ 的 $k$ 的取值种数，加上即可。这可以用二分解决。
时间复杂度：$O(n^2\log n)$，分数：72pts，不可过。
代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n , a[N] , b[N] , c[N] , ans;
signed 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++){
		for(int j = 1; j <= n; j++){
			if(a[i] >= b[j]) continue;
			//二分的前提是a[i] < b[j]
			int num = upper_bound(c + 1 , c + 1 + n , b[j]) - c;
			ans += n - num + 1;
			//二分找出所有大于b[j]的c[k]，ans累加
		}
	}
	cout << ans;
	return 0;
}

既然你都可以用二分来找出满足条件的 $k$，那我为什么不可以换一种枚举方式把满足条件的 $i$ 或 $j$ 也给找出来呢。
仔细看条件二：$a_i<b_j<c_k$。
有没有发现这个 $b_j$ 很特殊，他在这个不等式的中间。
我们现在把这个不等式变一下。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n , a[N] , b[N] , c[N] , ans;
signed 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);
	//排序，好进行二分
	for(int j = 1; j <= n; j++){
		int cnta = lower_bound(a + 1 , a + 1 + n , b[j]) - a - 1;
		int cntc = upper_bound(c + 1 , c + 1 + n , b[j]) - c;
		cntc = n - cntc + 1;
		//二分找出i的种类数和j的种类数
		ans += cnta * cntc;//乘法原理累计答案
	}
	cout << ans;
	return 0;
}