P8889 狠狠地切割(Hard Version) 题解
Double_Light
·
·
题解
题意简述
-
给定两个数列 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 数列被割成了几段。
注意：
例：若用 | 表示“狠狠地切割”处，则对于数列 | 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。
我们做一个 ```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``` 排序。
二分查找的参考代码如下：
```cpp
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. 第七个元素被“狠狠地切割”过，第二个片段结束，此时共有两个片段。
结合过程，我们找到了以下规律：
若一个元素未被“狠狠地切割”过，且下一个元素被“狠狠地切割”过，则会有一个新的片段产生。
那么，我们就写出来了代码：
```cpp
for(int i=1;i<n;i++){
if(!check(a[i])&&check(a[i+1]))ans++;
}
```
但别忘了，我们需加一个特判：
```cpp
if(!check(a[n]))ans++;
```
否则，是不能过 $a_n$ 没有被“狠狠地切割”的数据的。因为若 $a_n$ 没有被“狠狠地切割”过，则原来的代码是统计不到最后一个片段的。
---
最后，将两方面合并，加上输入输出和排序，我们就得到了完整的--
### AC 代码
```cpp
#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;
}
```