题解：AT_arc218_d [ARC218D] I like Increasing

dyc2022 · 2026-05-04 21:30:32 · 题解

更好的阅读体验

我们称序列 p 上的一组 (i, i+1) 满足 p_i < p_{i+1}，为一个上升位。题目要求的就是，使上升位数量最大的前提下，最短的子序列长度。

先不考虑区间查询。首先我们要考虑的是，给你一个排列 a，怎么求出它的一个子序列，使得上升位数量最大。

我们可以先得到答案上界：我们将序列 a 分成若干个极长的下降段，如 (4, 1, 5, 3, 7, 6, 2) 我们分成 (4, 1) , (5, 3), (7, 6, 2)。假设分成了 k 段，那么答案上界应该是 k-1。

这个为什么是上界很好理解：由于每一段递减，因此每一段内部不可能产生上升位；而相邻两个段至多产生一个上升位。因此总的上升位数量不会超过段数 -1。取到这个上界的条件也就是，每段至少选 1 个，相邻段会产生上升位。

接下来考虑一个基于构造的证明，可以在证明答案能取到 k-1 的同时，求解出最短的子序列长度。

• 对于第一段，显然选的数越小，后面的段越容易满足条件。因此我们选第一段的最小值。
• 假设我们前一个选的数字是 x，所属段是 i。那么
  • 如果 x> 第 i+1 段的最大值，那么我们在第 i+1 段无论选什么数都无法和第 i 段产生上升位，那就取不到上界了。因此需要在第 i 段多选一个数字来满足 i 和 i+1 段产生上升位。由于在当前段选小的数字是不劣的，我们选择当前第 i 段的最小值。容易证明当前段的最小值一定小于下一段的最大值，否则这两段应当合并称一个大段。
  • 如果 x< 第 i+1 段的最大值，那么一定可以通过在下一段选取合适的数字满足产生上升段的条件。由于在下一段选择尽可能小的数字更容易满足以后更多段的要求，因此我们选择 i+1 段中，最小的 >x 的数字。
• 当最后一个段有数字被选中的时候，答案被求得。

上述过程可以理解成，我们当前所选的数字在序列上跳的过程；而 x 会跳到哪里只和初始序列和 x 本身有关！

所以我们对于每个 x 预处理出 x 跳一步之后会跳到哪里。这个可以倍增优化。具体地，对于每次询问 [l, r]，如果 l, r 同属一段就输出 1；否则就从 l 所在段最小值开始跳，直到跳到 r 所属段为止即可。

复杂度 O(n \log n)。

#include<bits/stdc++.h>
#define endl '\n'
#define N 200006
using namespace std;
int n,q,c,a[N],bel[N],pos[20][N];
pair<int,int> b[N];
main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1,j;i<=n;i=j+1)
    {
        for(j=i;j<n&&a[j]>a[j+1];j++);
        b[++c]={i,j};
        for(int k=i;k<=j;k++)bel[k]=c;
    }
    bel[n+1]=c+1;
    for(int j=0;j<20;j++)
        for(int i=1;i<=n+1;i++)pos[j][i]=n+1;
    for(int i=1;i<=n;i++)
    {
        if(bel[i]==c)continue;
        if(a[i]>a[b[bel[i]+1].first])pos[0][i]=b[bel[i]].second;
        else {
            int l=b[bel[i]+1].first;
            int r=b[bel[i]+1].second;
            while(l<=r)
            {
                int mid=l+r>>1;
                if(a[mid]>a[i])pos[0][i]=mid,l=mid+1;
                else r=mid-1;
            }
        }
    }
    for(int i=1;i<20;i++)
        for(int j=1;j<=n;j++)pos[i][j]=pos[i-1][pos[i-1][j]];
    while(q--)
    {
        int l,r; scanf("%d%d",&l,&r);
        if(bel[l]==bel[r]) {printf("1\n"); continue;}
        int ans=1,st=b[bel[l]].second;
        for(int i=19;~i;i--)
            if(bel[pos[i][st]]<bel[r])ans+=1<<i,st=pos[i][st];
        printf("%d\n",ans+1);
    }
    return 0;
}