[题解] 2026 牛客暑期多校训练营 4 F. 23 子序列（值域 DP + 离线区间询问）

题目链接：F. 23 子序列

比赛：2026 牛客暑期多校训练营 4

TAG：动态规划、值域线段树、离散化、区间询问、滚动数组

题意

定义正整数序列 \(b=(b_1,b_2,\ldots,b_m)\) 是好的，当且仅当对每个 \(2\le i\le m\)，均满足

\[2b_{i-1}\le b_i\le 3b_{i-1}. \]

长度为 \(1\) 的序列总是好的。

给定长度为 \(n\) 的正整数序列 \(a\)，有 \(q\) 次询问。每次给出区间 \([l,r]\)，求 \(a_l,a_{l+1},\ldots,a_r\) 中最长好子序列的长度。

子序列不要求连续，但必须保持原序列中的相对顺序。

数据范围：

\[1\le n,q\le 2\times 10^5,\qquad 1\le a_i\le 10^{18}. \]

一、从单次询问的动态规划开始

假设只需要处理一个固定区间，可以定义

\[dp_i=\text{以位置 }i\text{ 结尾的最长好子序列长度}. \]

若位置 \(j<i\) 能够转移到位置 \(i\)，需要满足

\[2a_j\le a_i\le 3a_j. \]

于是有

\[dp_i=1+\max_{\substack{j<i\\2a_j\le a_i\le 3a_j}}dp_j. \]

这个转移可以用值域线段树优化到一次 \(O((r-l+1)\log n)\)，但若对 \(q\) 个询问分别计算，总复杂度仍然无法承受。

真正的难点不在于“如何求一个区间的答案”，而在于：

能否预处理一种状态，使它既能按子序列长度递推，又能快速判断子序列是否完整落入任意询问区间？

二、改变状态：记录最大的起点

定义

\[f_{k,i} \]

表示：

所有长度为 \(k\)、恰好在位置 \(i\) 结束的好子序列中，最大的起点位置。

若不存在这样的子序列，则令 \(f_{k,i}=0\)。

长度为 \(1\) 时，只选择 \(a_i\)，因此

\[f_{1,i}=i. \]

这个状态记录“最大的起点”，是为了方便判断一条子序列能否完整落在询问区间 \([l,r]\) 内。

为什么取最大的起点

固定长度 \(k\) 和终点 \(i\) 后，假设存在两条好子序列，它们的起点分别为 \(s_1<s_2\)。

对后续转移而言，两条序列的长度相同、末尾都是 \(a_i\)，能否继续接上某个 \(a_j\) 只由末尾值 \(a_i\) 决定，与起点无关；
对区间询问而言，起点越靠右越优。如果起点为 \(s_1\) 的序列能落入 \([l,r]\)，那么 \(s_2>s_1\) 的序列也更容易满足 \(s_2\ge l\)。

因此，在长度和终点相同的所有状态中，只保留最大的起点不会影响任何后继转移，也不会影响任何询问的可行性判断。这是一种支配关系：较大的起点完全支配较小的起点。

三、状态转移

设某条长度为 \(k\) 的好子序列在位置 \(i\) 结束，其倒数第二个元素位于位置 \(j\)。必须满足

\[j<i \]

以及

\[2a_j\le a_i\le 3a_j. \]

将不等式改写为对前驱值 \(a_j\) 的限制：

\[\left\lceil\frac{a_i}{3}\right\rceil\le a_j\le \left\lfloor\frac{a_i}{2}\right\rfloor. \]

因此

\[f_{k,i}= \max_{\substack{j<i\\ \lceil a_i/3\rceil\le a_j\le\lfloor a_i/2\rfloor}} f_{k-1,j}. \]

也就是说，对于固定的长度 \(k\)，我们从左向右扫描位置 \(i\)，需要查询所有已经处理过的位置中，数值落在某个区间内的最大 \(f_{k-1,j}\)。

这正是值域线段树。

四、值域离散化

因为 \(a_i\le 10^{18}\)，无法直接按照数值建立线段树。

将所有 \(a_i\) 排序、去重，得到离散化数组 \(b\)。记：

rk[i]：\(a_i\) 在离散化数组中的下标；
vl[i]：第一个满足 \(b_x\ge \lceil a_i/3\rceil\) 的下标；
vr[i]：最后一个满足 \(b_x\le \lfloor a_i/2\rfloor\) 的下标。

于是转移变为：

\[f_{k,i}=\max_{x\in[vl_i,vr_i]}\text{tree}[x]. \]

扫描位置 \(i\) 时：

先查询值域区间 \([vl_i,vr_i]\)，计算 \(f_{k,i}\)；
再把上一层状态 \(f_{k-1,i}\) 插入数值 \(a_i\) 对应的位置。

必须先查询再插入，这样线段树中只包含位置严格小于 \(i\) 的状态，保证子序列下标递增。

五、为什么长度最多只有 60

好序列中的每个数至少是前一个数的两倍：

\[b_i\ge 2b_{i-1}. \]

因此

\[b_m\ge 2^{m-1}b_1\ge 2^{m-1}. \]

又因为所有数都不超过 \(10^{18}\)，所以

\[2^{m-1}\le 10^{18}. \]

而

\[2^{59}\le 10^{18}<2^{60}, \]

故

\[m\le 60. \]

因此只需计算至多 \(60\) 层动态规划。

代码还利用整个数组的最小值 \(mn\) 和最大值 \(mx\)，进一步估计实际可能出现的最大长度。

任意长度为 \(m\) 的好子序列都满足

\[b_m\ge 2^{m-1}b_1\ge 2^{m-1}mn, \]

同时 \(b_m\le mx\)，所以必须有

\[2^{m-1}mn\le mx. \]

代码从 \(x=mn\) 出发不断乘 \(2\)，计算满足这一必要条件的最大长度：

int lim=1;
ll x=mnv;
while(lim<K&&lim<n&&x<=mxv/2){x*=2;lim++;
}

判断写成 x<=mxv/2 而不是先计算 2*x<=mxv，可以避免乘法溢出。这个上界可能比真实答案更大，但绝不会小于真实答案，因此用来限制 DP 层数是安全的。

六、滚动数组

第 \(k\) 层只依赖第 \(k-1\) 层，因此不需要保存完整的 \(f_{k,i}\)。

使用

int f[2][N];

并令

int now=k&1;
int pre=now^1;

其中：

f[now][i] 表示当前第 \(k\) 层；
f[pre][i] 表示上一层 \(k-1\)。

这样动态规划状态本身的空间由 \(O(60n)\) 降为 \(O(n)\)。不过为了回答区间询问，仍需保留每一层的前缀最大值数组 \(mx\)，因此总空间复杂度仍为 \(O(60n)\)。

七、如何回答区间询问

定义

\[mx_{k,i}=\max_{1\le j\le i}f_{k,j}. \]

也就是：

所有结束位置不超过 \(i\) 的长度为 \(k\) 的好子序列中，最大的起点位置。

对于询问 \([l,r]\)，区间中存在长度为 \(k\) 的好子序列，当且仅当

\[mx_{k,r}\ge l. \]

必要性

若区间 \([l,r]\) 中存在长度为 \(k\) 的好子序列，设其终点为 \(j\)，则

\[l\le j\le r \]

并且其起点不小于 \(l\)。所以

\[f_{k,j}\ge l, \]

进而

\[mx_{k,r}\ge f_{k,j}\ge l. \]

充分性

若

\[mx_{k,r}\ge l, \]

则存在某个 \(j\le r\)，使得

\[f_{k,j}\ge l. \]

由 \(f_{k,j}\) 的定义，存在一条长度为 \(k\)、终点为 \(j\)、起点为 \(f_{k,j}\ge l\) 的好子序列。

同时必然有

\[f_{k,j}\le j. \]

因此 \(f_{k,j}\ge l\) 可以推出 \(j\ge l\)。子序列的下标严格递增，所以所有中间位置都位于起点与终点之间。这条子序列的起点和终点都在 \([l,r]\) 内，整条子序列自然也完全位于询问区间中。

这里也是为什么可以查询前缀 \([1,r]\)，而不必单独查询结束位置区间 \([l,r]\)：若终点 \(j<l\)，则起点一定不超过 \(j\)，不可能满足 \(f_{k,j}\ge l\)。

八、二分答案

若区间中存在长度为 \(k\) 的好子序列，那么删去最后若干个元素后，也一定存在长度为 \(1,2,\ldots,k-1\) 的好子序列。

因此可行性关于长度具有单调性，可以在 \([1,\text{maxlen}]\) 上二分最大的可行长度。

判断条件为

mx[mid][r]>=l

每次询问的复杂度为 \(O(\log 60)\)。

九、迭代线段树

本题使用大小为 \(2\times len\) 的紧凑式迭代线段树：

t[len] 到 t[2*len-1] 是叶子；
离散化下标 \(p\) 对应叶子 p+len；
父结点为 p>>1；
左、右儿子分别为 p<<1 和 p<<1|1。

单点取最大值

void update(int p,int v){p+=len;if(t[p]>=v) return;t[p]=v;for(p>>=1;p;p>>=1){int nv=max(t[p<<1],t[p<<1|1]);if(t[p]==nv) break;t[p]=nv;}
}

先修改叶子，再不断向上更新祖先。

若某一层结点的值没有发生变化，则更高层也不会变化，可以直接退出。

区间最大值查询

代码将闭区间 \([l,r]\) 转换为左闭右开区间 \([l,r+1)\)：

inline int query(int l,int r){int ans=0;for(l+=len,r+=len+1;l<r;l>>=1,r>>=1){if(l&1) ans=max(ans,t[l++]);if(r&1) ans=max(ans,t[--r]);}return ans;
}

其中：

若 l 是右儿子，则该结点无法和左兄弟一起向上合并，需要单独统计；
若 r 是右边界对应父区间的右端，则先执行 --r，再单独统计；
随后两端同时除以 \(2\)，进入上一层。

十、正确性证明

引理 1

对于任意 \(k\ge 1\) 和位置 \(i\)，动态规划计算出的 \(f_{k,i}\) 等于所有长度为 \(k\)、恰好在位置 \(i\) 结束的好子序列中的最大起点。

证明：

当 \(k=1\) 时，只选择位置 \(i\)，因此 \(f_{1,i}=i\)，结论成立。

假设结论对 \(k-1\) 成立。考虑长度为 \(k\)、在位置 \(i\) 结束的好子序列，其倒数第二个位置一定为某个 \(j<i\)，并满足

\[2a_j\le a_i\le 3a_j. \]

根据归纳假设，以 \(j\) 结尾的长度为 \(k-1\) 的好子序列的最大起点为 \(f_{k-1,j}\)。将 \(a_i\) 接在这条序列后即可得到长度为 \(k\) 的合法序列；反过来，任意长度为 \(k\)、以 \(i\) 结尾的好子序列删去最后一个元素后，也一定对应某个合法前驱 \(j\)。

因此，枚举所有合法 \(j\) 并取最大的 \(f_{k-1,j}\)，恰好得到所有长度为 \(k\)、在 \(i\) 结束的好子序列中的最大起点。证毕。

引理 2

处理位置 \(i\) 时，值域线段树中恰好保存了所有位置 \(j<i\) 的上一层状态 \(f_{k-1,j}\)。

证明：

位置按照从小到大的顺序处理。每个位置都在完成当前查询后，才将自己的上一层状态插入线段树。

因此处理位置 \(i\) 前，位置 \(1,2,\ldots,i-1\) 均已插入，而位置 \(i,i+1,\ldots,n\) 均未插入。若多个位置的数值相同，线段树叶子维护这些位置状态的最大值，仍与转移所需信息完全一致。证毕。

引理 3

对于询问 \([l,r]\)，其中存在长度为 \(k\) 的好子序列，当且仅当 \(mx_{k,r}\ge l\)。

证明：

必要性与充分性已在第七部分分别证明。证毕。

定理

算法对每个询问输出的答案均为区间内最长好子序列的长度。

证明：

由引理 1 和引理 2，算法正确计算所有需要的动态规划状态；由引理 3，条件 mx[k][r]>=l 能准确判断区间中是否存在长度为 \(k\) 的好子序列。

可行性关于 \(k\) 单调，二分得到的最大可行 \(k\) 即为区间内最长好子序列长度。证毕。

十一、复杂度分析

设实际计算的最大长度为 \(L\)，其中 \(L\le 60\)。

离散化与合法值域预处理：\(O(n\log n)\)；
动态规划：每层进行 \(n\) 次线段树查询和至多 \(n\) 次修改，共 \(O(Ln\log n)\)；
每次询问二分答案：\(O(\log L)\)。

总时间复杂度为

\[O(Ln\log n+q\log L), \qquad L\le 60. \]

空间复杂度为

\[O(Ln+n), \]

主要空间来自用于询问的前缀最大值数组 mx。

十二、实现细节与边界情况

当合法前驱值域为空，即 vl[i]>vr[i] 时，当前状态直接为 \(0\)，不能调用区间查询。
线段树初值为 \(0\)，同时 \(0\) 也表示对应好子序列不存在。
长度为 \(1\) 的好子序列始终存在，所以每个非空询问的答案至少为 \(1\)。
某一层 \(k\) 完全不存在可行状态时，更长的好子序列也不可能存在，可以立即停止预处理。
a[i]、上下界和倍增变量必须使用 long long；起点、终点和 DP 值只需存下标，使用 int 即可。

十三、完整代码

展开完整代码（共 134 行）收起代码

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int K=60;
const int N=2e5+5;
ll a[N];
int rk[N],vl[N],vr[N];
// f[k&1][i]：长度为k、在位置i结束的好子序列的最大起点
int f[2][N];
// mx[k][i]：结束位置不超过i的长度k好子序列的最大起点
int mx[K+1][N];
int t[N<<1];
int len;
// 清空当前长度对应的值域线段树
inline void clear_tree(){memset(t,0,sizeof(int)*(len<<1));
}
// 在离散化位置p处执行单点取最大值
inline void update(int p,int v){p+=len;if(t[p]>=v) return;t[p]=v;for(p>>=1;p;p>>=1){int nv=max(t[p<<1],t[p<<1|1]);// 当前结点未变化，则更高层也不会变化if(t[p]==nv) break;t[p]=nv;}
}
// 查询离散化闭区间[l,r]中的最大起点
inline int query(int l,int r){int ans=0;// 将闭区间[l,r]转化为左闭右开区间[l,r+1)for(l+=len,r+=len+1;l<r;l>>=1,r>>=1){if(l&1) ans=max(ans,t[l++]);if(r&1) ans=max(ans,t[--r]);}return ans;
}
void solve(){int n,q;cin>>n>>q;vector<ll>b;b.reserve(n);ll mnv=LLONG_MAX,mxv=0;for(int i=1;i<=n;i++){cin>>a[i];b.push_back(a[i]);mnv=min(mnv,a[i]);mxv=max(mxv,a[i]);}// 离散化所有出现过的数值sort(b.begin(),b.end());b.erase(unique(b.begin(),b.end()),b.end());len=b.size();for(int i=1;i<=n;i++){// a[i]在离散化数组中的位置rk[i]=lower_bound(b.begin(),b.end(),a[i])-b.begin();/*前驱a[j]需要满足：2*a[j]<=a[i]<=3*a[j]即ceil(a[i]/3)<=a[j]<=floor(a[i]/2)*/ll low=(a[i]+2)/3;ll high=a[i]/2;vl[i]=lower_bound(b.begin(),b.end(),low)-b.begin();vr[i]=upper_bound(b.begin(),b.end(),high)-b.begin()-1;}// 根据全局最小值与最大值估计实际可能的最大答案int lim=1;ll x=mnv;while(lim<K&&lim<n&&x<=mxv/2){x*=2;lim++;}// 长度为1时，起点与终点均为当前位置for(int i=1;i<=n;i++){f[1][i]=i;mx[1][i]=i;}int maxlen=1;// 按好子序列长度逐层进行动态规划for(int k=2;k<=lim;k++){int now=k&1;int pre=now^1;clear_tree();mx[k][0]=0;bool exist=false;for(int i=1;i<=n;i++){/*此时线段树中只保存位置j<i的上一层状态。查询合法前驱值域，得到长度为k的最大起点。*/f[now][i]=0;if(vl[i]<=vr[i]){f[now][i]=query(vl[i],vr[i]);}if(f[now][i]) exist=true;// 对结束位置维护前缀最大值，便于O(1)判断固定长度是否可行mx[k][i]=max(mx[k][i-1],f[now][i]);// 查询后再插入当前位置，保证前驱位置严格小于iif(f[pre][i]){update(rk[i],f[pre][i]);}}// 不存在长度为k的好子序列时，更长的也一定不存在if(!exist) break;maxlen=k;}while(q--){int l,r;cin>>l>>r;int ans=1;int ql=2,qr=maxlen;// 可行性关于长度单调，二分最大的可行长度while(ql<=qr){int mid=(ql+qr)>>1;if(mx[mid][r]>=l){ans=mid;ql=mid+1;}else{qr=mid-1;}}cout<<ans<<endl;}
}
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);solve();return 0;
}