自动搬运

查看原文

来自洛谷，原作者为

	Double_Light 身虽位于苍穹一粟，心亦向往若尘繁星。

搬运于2025-08-24 22:43:27，当前版本为作者最后更新于2022-12-11 14:20:31，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题意简述

• 给定两个数列 $a_{1,2,...,n},b_{1,2,...,m}$，$-10^{18} \ge a_i,b_i \ge 10^{18}$。

• 若 $a_i=b_j$，则 $a$ 数列沿着 $a_i$ 处割成左右两段，称为“狠狠地切割”。

• 求最后 $a$ 数列被割成了几段。

注意：

• 若 $a$ 数组有两个相邻的元素都被“狠狠地切割”过，则两元素中间不算一个片段。

• 若 $a$ 数组的第一个元素被“狠狠地切割”，则数组左边界不算一个片段。

例：若用 $|$ 表示“狠狠地切割”处，则对于数列 $|$ $4$ $5$ $|$ $|$ $2$ $|$ 而言，只有 $4$ $5$ 和 $2$ 属于片段。

题目分析

对于本题而言，代码主要部分为进行切割和统计片段两部分。

---

第一部分--进行切割

注意数据范围：

对于 $100\%$ 的数据，保证$1\leq n,m\leq5\times10^5,1≤n,m≤5×10^5,-10^{18}\leq a_i,b_i\leq10^{18}-10^{18}≤a_i,b_i ≤10 ^{18}$,序列 $b$ 中的元素两两不同。

由于 $n$ 达到了 $5×10^5$，时间复杂度应小于 $\Theta(n^2)$， 所以我们不能用两重循环的方式来枚举 $a_i$ 和 $b_j$。

这时，我们可以使用一个巨好用的算法：二分。

我们来简单介绍一下二分（懂二分查找的读者可跳过本段）。

二分，此处指二分查找，是一种特殊的分治。

我们看看度娘对二分查找的解释：

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

通俗来说，也就是给定一个长度为 $n$ 的有序数列（如升序）和一个将查找的数 $x$，将数列中最中间一个元素（称为 $a_i$）与 $x$ 进行比较，若 $x=a_i$，则数列中间的元素与 $x$ 的值相等。若 $x>a_i$，则二分查找从 $a_{i+1}$ 至 $a_n$ 的数，若 $x>a_i$，则二分查找从 $a_1$ 至 $a_{i-1}$ 的数。

这样做的好处在于，每次查找都可以帮我们排除一半的数，最多仅需 $\log n$ 次就可以找到 $x$ 在不在数列中，以及是数列的第几项。

那么，我们怎么用代码实现呢？

若对 $a_i$ 进行二分查找，则我们定义三个变量 $l,r,mid$，令 $l=1$，$r=n$，$mid$ 为 $l$ 和 $r$ 的平均数，即 $(l+r)/2$。

$l$ 代表二分的左端点，$r$ 代表二分的右端点，而 $mid$ 是数列最中间一个元素，将与 $x$ 进行比较。

我们做一个 while() 循环，循环条件是 l<=r，意思是还有 $b_l\sim b_r$ 可能等于 $x$，若 $l>r$，则没有一个数 $b_j$ 可能等于 $a_i$。

循环内部则在更新 $mid$ 的值后将 $b_{mid}$ 与 $a_i$ 比较。

如果两者相等，则 $a_i$ 将被“狠狠地切割”。

如果 $b_{mid}<a_i$,则 $l=mid+1$，查找区间缩小，仅剩原来的右半区。

否则 $r=mid-1$，查找区间同样缩小，仅剩原来的左半区。

将本部分写成函数，对本题而言更方便。

别忘了先将 $b$ 数组进行 sort 排序。

二分查找的参考代码如下：

bool check(long long k) {
	long long l=1,r=m,mid;
	while(l<=r){
		mid=(l+r)/2;
		if (k<b[mid])r=mid-1;
		else if(k>b[mid])l=mid+1;
		else return 1;
	}
	return 0;
}

---

第二部分--统计片段

我们以数列 $|$ $4$ $5$ $|$ $|$ $2$ $|$ 为例，进行这部分的分析。

这是我们手动统计片段的过程：

1. 第一个元素被“狠狠地切割”过，此时并没有片段。

2. 第二个元素未被“狠狠地切割”，属于第一个片段。

3. 第三个元素与第二个元素间没有被“狠狠地切割”，两个元素同属于第一个片段。

4. 第四个元素被“狠狠地切割”过，第一个片段结束，此时共有一个片段。

5. 第五个元素也被“狠狠地切割”过，但并没有新的片段产生。

6. 第六个元素未被“狠狠地切割”，属于第二个片段。

7. 第七个元素被“狠狠地切割”过，第二个片段结束，此时共有两个片段。

结合过程，我们找到了以下规律：

若一个元素未被“狠狠地切割”过，且下一个元素被“狠狠地切割”过，则会有一个新的片段产生。

那么，我们就写出来了代码：

for(int i=1;i<n;i++){
	if(!check(a[i])&&check(a[i+1]))ans++;
}

但别忘了，我们需加一个特判：

if(!check(a[n]))ans++;

否则，是不能过 $a_n$ 没有被“狠狠地切割”的数据的。因为若 $a_n$ 没有被“狠狠地切割”过，则原来的代码是统计不到最后一个片段的。

---

最后，将两方面合并，加上输入输出和排序，我们就得到了完整的--

AC 代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long n,m,x,a[500005],b[500005],ans;
bool check(long long k) {
	long long l=1,r=m,mid;
	while(l<=r){
		mid=(l+r)/2;
		if (k<b[mid])r=mid-1;
		else if(k>b[mid])l=mid+1;
		else return 1;
	}
	return 0;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(int i=1;i<=m;i++)scanf("%lld",&b[i]);
	sort(b+1,b+m+1);
	if(!check(a[n]))ans++;
	for(int i=1;i<n;i++){
		if(!check(a[i])&&check(a[i+1]))ans++;
	}
	cout<<ans;
	return 0;
}