美丽的序列

定义长度为 $len$ 且满足 $\max\limits_{i=1}^{len} w_i - \min\limits_{i=1}^{len} w_i +1 = len$ 的序列 $w$ 为美丽的序列

给定长度为 $n$ 的排列 $a,b$,求有多少个美丽的序列同时是 $a,b$ 的子序列,$1 \leq n \leq 10^5$。

题目链接

贪心、双指针

问题有单调性却无法二分时应该考虑双指针、优先队列或者三分、决策单调性、斜率优化。单调性在绝大多数题目中是有用的。发现问题性质后应当尽量给出能够利用性质的做法。

如果值域 $[l,r]$ 对应的子序列同时在 $a,b$ 中出现,那么 $[l,r]$ 的任意子区间对应的子序列也会同时在 $a,b$ 中出现。容易想到枚举值域下界 $i$ 再二分这个值域下界对应的上界的做法,但是无法快速处理二分需要的信息,这个做法的复杂度是 $O(n^2)$。

考虑双指针,对于左端点 $l$ 判断值域区间 $[l,r+1]$ 对应的子序列在 $a,b$ 中是否一致,如果一致则扩展右端点。不一致时扩展左端点,由于值域区间 $[l,r]$ 合法,扩展后得到的值域区间 $[l-1,r]$ 必定合法,如此一来指针 $l,r$ 都只会增加至多 $n$ 次。

使用 set 维护当前合法值域对应的子序列,时间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
using namespace std;
int n,a[100'005],b[100'005],pa[100'005],pb[100'005];
set<int> sa,sb;
long long ans;
bool success(int x){
    auto ita=sa.lower_bound(pa[x]),itb=sb.lower_bound(pb[x]);
    return a[*ita]==b[*itb]&&a[*prev(ita)]==b[*prev(itb)];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    for(int i=1;i<=n;i++) pa[a[i]]=i,pb[b[i]]=i;
    sa.emplace(0),sa.emplace(n+1);
    sb.emplace(0),sb.emplace(n+1);
    int pos=1;
    sa.emplace(pa[1]),sb.emplace(pb[1]);
    for(int i=1;i<=n;i++){
        while(pos+1<=n&&success(pos+1)){
            ++pos;
            sa.emplace(pa[pos]);
            sb.emplace(pb[pos]);
        }
        ans+=pos-i+1;
        sa.erase(pa[i]),sb.erase(pb[i]);
    }
    printf("%lld\n",ans);
    return 0;
}
最后修改:2024 年 10 月 17 日
如果觉得我的文章对你有用,请随意赞赏