题解：AT_abc248_h [ABC248Ex] Beautiful Subsequences

· · 题解

这么爽。

分析

拿到这种题的时候相信你已经秒了，因为这题纯套路。

式子的 r-l 不好看，换成区间长度，即：\max\limits_{i=l}^{r} P_i - \min\limits_{i=l}^{r} P_i -(r-l+1) \le k-1（虽然做完之后会发现它没什么用，但是曼波喜欢，别喷曼波 pwp）。

考虑序列上分治。定义 f(L,R) 表示区间 [L,R] 的答案，则 f(L,R)=f(L,mid)+f(mid+1,R)+w(L,R)，其中 w(L,R) 表示跨 mid 的答案。

难点在 w(L,R) 怎么算。对于一个 l|L \le l \le mid，找到最大的 j 与 k，使得：\min\limits_{i=l}^{mid} P_i = \min\limits_{i=l}^{j} P_i \land \max\limits_{i=l}^{mid} P_i = \max\limits_{i=l}^{k} P_i。得到 3 种情况：

对于第 1 种情况，有：

max-min+l-1-k \le r

所以任意一个 [\max(mid+1,max-min+l-1-k),\min(j,k)] 中的 r 都满足条件。

对于第 2 种情况，分类讨论一下。拿 j\le k 的情况举例，此时 max 一定。令 a_i=\min\limits_{j=mid+1}^{i} P_j,b_i =\max\limits_{j=mid+1}^{i} P_j。有：

max-a_r+l-1-k \le r\\ max+l-1-k \le r+a_r

可以用任意方式维护，这里我使用的是离线后树状数组。j >k 的情况同理，这里不再赘述。

对于第 3 种情况，有：

b_r-a_r+l-1-k \le r\\ l-1-k \le r+a_r-b_r

也可以用任意方式维护。

复杂度为 O(n \log n) \sim O(n \log^2 n)。我的做法是 O(n \log^2 n) 的。

代码

il void work(int l,int r){
    if(l==r){
        ans+=(a[l]-a[l]-(r-l+1)<=K);
        return ;
    }
    int mid=l+r>>1;
    work(l,mid),work(mid+1,r);
    for(re int i=mid;i<=r+1;++i){
        v1[i].clear(),
        v2[i].clear(),
        v3[i].clear();
    }
    Max[mid+1]=Min[mid+1]=a[mid+1];
    for(re int i=mid+2;i<=r;++i){
        Max[i]=max(Max[i-1],a[i]),
        Min[i]=min(Min[i-1],a[i]);
    }
    int mx=a[mid],mi=a[mid];
    for(re int L=mid,j=mid,k=mid;L>=l;--L){
        mi=min(mi,a[L]),mx=max(mx,a[L]);
        while(j+1<=r&&Min[j+1]>=mi) ++j;
        while(k+1<=r&&Max[k+1]<=mx) ++k;
        ans+=max(0ll,min(j,k)-max(mx-mi+L-1-K,mid+1)+1);//1
        if(j<=k){//2.1
            int s=+mx+L-1-K;
            v1[min(j,k)].push_back({s,-1});
            v1[max(j,k)].push_back({s, 1});
        }
        else{//2.2
            int s=-mi+L-1-K;
            v2[min(j,k)].push_back({s,-1});
            v2[max(j,k)].push_back({s, 1});
        }
        int s_=L-1-K;
        v3[max(j,k)+1].push_back(s_);//3
    }

    for(re int R=mid+1;R<=r;++R){//2.1
        add(Min[R]+R,1);
        for(auto x:v1[R]) ans+=x.y*query(x.x);
    }
    for(re int R=mid+1;R<=r;++R) add(Min[R]+R,-1);

    for(re int R=mid+1;R<=r;++R){//2.2
        add(R-Max[R],1);
        for(auto x:v2[R]) ans+=x.y*query(x.x);
    }
    for(re int R=mid+1;R<=r;++R) add(R-Max[R],-1);

    for(re int R=r;R>=mid+1;--R){//3
        add(R+Min[R]-Max[R],1);
        for(auto x:v3[R]) ans+=query(x);
    }
    for(re int R=r;R>=mid+1;--R) add(R+Min[R]-Max[R],-1);
    return ;
}