当dp的转移常数空间非常大比如dp[100000][100000]但是dp内维护的值非常小比如1-10我们就可以选择维护dp[100000][10]或dp[10][100000];而值代表另一个维度比如 l r的中间翻倍子序列长度翻倍子序列很小所以可以维护从任意 r 结尾子序列长度为 x 的最小 l 来极大缩小常数。DP 状态的某一维通常是长度很小≤60但每一层的转移涉及在满足某个权值条件的历史状态中找最优值需要用线段树/树状数组加速。一、方法总结核心思想步骤做什么为什么① 发现长度上界证明/观察到答案枚举长度 ≤ O(logV)可以逐长度枚举不会 TLE② 定义 DP 状态fi,j 以 i 结尾、长度为 j 的某种极值通常是最小起点 / 最大终点把选子序列转化为递推③ 值域限制 → 区间查询转移条件形如 L≤ak≤R转化为在离散化权值上的区间查询线段树/树状数组直接上④ 控制下标顺序正序/倒序枚举 i保证查到的都是前面/后面的状态不用再管下标维线段树只管权值⑤ 离线/半在线回答询问每算完一层顺手用后缀/前缀最值更新所有询问的答案免去存所有 fi,j适用场景速判看到以下特征就可以往这个方向想子序列需要满足某种乘法/指数型增长条件2x≤y≤3x、y≥kx、yy×c 等//dp值限制在非常小的范围多次区间询问求最长合法子序列长度转移条件是前面找一个满足条件的位置取某个最值常见变体变体改哪里条件是 y≥2x只有下界rightId设为 m无穷大条件是 y2x 精确相等区间退化为单点查询用数组/map 就行求的是最长长度的具体方案多记一个pre指针回溯询问强制在线把所有 fi,j 存下来对每列做 RMQ/线段树长度不是 log 级而是 O(n)失效得换思路单调栈/贪心/决策单调性二、通用板子定义序列 b (b1, b2, . . . , bm) 是合法的当且仅当对于所有 2 ≤ i ≤ m都有2bi−1 ≤ bi ≤ 3bi−1.特别地长度为 1 的序列一定合法。给定一个长度为 n 的正整数序列 a需要回答 q 个区间询问。每次给定区间 [l, r]求 al, al1, . . . , ar 中最长合法子序列的长度。所选元素不要求连续但必须保持相对顺序。1 ≤ n, q ≤ 2 · 10e51 ≤ ai ≤ 10e181 ≤ l ≤ r ≤ n。核心思路1. DP 状态设计设 fi,j 表示以第 i 个元素结尾、长度为 j 的合法子序列中最靠左的开头位置即最小的起始下标。当 j1 时fi,1i单个元素自己就是合法子序列。当 j1 时我们要找一个 ki满足 2ak≤ai≤3ak且 fk,j−1 尽可能小这样得到的序列整体更靠右更容易被包含在询问区间里。转移方程fi,jki2ak≤ai≤3akminfk,j−12. 用线段树加速转移转移有两个限制下标限制ki我们只需从小到大或从大到小枚举 i保证只用到之前的 k。权值限制ak∈[⌈ai/3⌉,⌊ai/2⌋]等价于 ai∈[2ak,3ak]。代码采用了倒序枚举 i从 n 到 1的巧妙方式维护一棵线段树以离散化后的 a 值为下标线段树每个节点存储已经遍历过的元素下标更大的 fk,j−1 的最小值。对于当前 i需要找的是后面的某个 kki满足 2ai≤ak≤3ai。这正好对应线段树上区间 [leftIdi,rightIdi] 的查询。查询得到的最小值就是 fi,j代码中记为cur[i]。然后把当前的 fi,j−1即prev[i]更新进线段树供更前面的 i 使用。这样我们在 O(logm)m 为离散化后数值种类时间内完成了单次转移。3. 如何回答区间询问对于一个询问 [l,r]如果存在某个 i∈[l,r] 使得 fi,j≥l那就说明能在 [l,r] 内找到一个长度为 j 的合法子序列开头 ≥l结尾 i≤r。代码中使用了一个等价但更易实现的判断计算出cur[i]即 fi,j后求一个后缀最小值数组suf[i] min_{k \ge i} cur[k]。如果suf[l] r说明存在一个结尾 ≥l 且开头 ≤r 的长度为 j 的序列结合 f 的定义这个序列整体落在 [l,r] 内的条件被满足于是更新答案为 j。由于我们是按长度 j2,3,… 依次计算的并且只要当前长度可行就更新ans[id] len最终每个询问就会留下最大可行长度。核心结构//涉及权值线段树离散化不是最基础的板子仅面向类似题目// // 通用板子逐层DP 权值线段树优化转移 // 解决区间询问最长合法子序列长度 // 时间复杂度O(n log n * max_len) // #include bits/stdc.h using namespace std; const int INF 1e9; const int MAXN 200005; // ---------- 权值线段树区间最小值---------- struct SegMin { int n; vectorint t; SegMin(int m) { n 1; while (n m) n 1; t.assign(2 * n, INF); } void update(int p, int val) { if (val INF) return; int x p n - 1; if (t[x] val) return; t[x] val; for (x 1; x; x 1) t[x] min(t[x1], t[x1|1]); } int query(int l, int r) { if (l r) return INF; int res INF; l n - 1; r n - 1; while (l r) { if (l 1) res min(res, t[l]); if (!(r 1)) res min(res, t[r--]); l 1; r 1; } return res; } }; // ---------- 主逻辑 ---------- void solve(const vectorlong long a, const vectorpairint,int queries) { int n a.size() - 1; // a[1..n] int q queries.size(); // --- Step 1: 离散化 --- vectorlong long vals(a.begin() 1, a.end()); sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); int m vals.size(); auto get_id [](long long x) { return lower_bound(vals.begin(), vals.end(), x) - vals.begin() 1; }; auto get_end [](long long x) { // upper_bound 版本 return upper_bound(vals.begin(), vals.end(), x) - vals.begin(); }; vectorint pos(n 1), L(n 1), R(n 1); for (int i 1; i n; i) { pos[i] get_id(a[i]); L[i] get_id(a[i] * 2); // ← 题目条件2*a[i] ≤ a[k] R[i] get_end(a[i] * 3 - 1); // ← 题目条件a[k] ≤ 3*a[i] } // --- Step 2: 初始化长度为1 --- vectorint prev(n 2); for (int i 1; i n; i) prev[i] i; // --- Step 3: 逐层 DP --- vectorint cur(n 2); vectorint suf(n 2); vectorint ans(q, 1); SegMin seg(m); for (int len 2; ; len) { seg SegMin(m); // 重置 fill(cur.begin(), cur.end(), INF); // 倒序枚举找后面的 k i for (int i n; i 1; --i) { if (L[i] R[i]) cur[i] seg.query(L[i], R[i]); seg.update(pos[i], prev[i]); } // 后缀最小值 int best INF; for (int i n; i 1; --i) { best min(best, cur[i]); suf[i] best; } if (best INF) break; // 这一层已经没有合法序列了 // 更新所有询问 for (int id 0; id q; id) { int l queries[id].first, r queries[id].second; if (suf[l] r) ans[id] len; } prev.swap(cur); } // 输出 for (int x : ans) cout x \n; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin n q; vectorlong long a(n 1); for (int i 1; i n; i) cin a[i]; vectorpairint,int queries(q); for (int i 0; i q; i) cin queries[i].first queries[i].second; solve(a, queries); return 0; }权值线段树SegMinstruct SegMin { int n; vectorint t; SegMin(int m) { n 1; while (n m) n 1; t.assign(2 * n, INF); } void update(int p, int val) { ... } int query(int l, int r) { ... } };普通线段树权值线段树下标含义数组的位置第几个元素元素的值本身叶子节点对应a[i]这个位置的数对应值为x的数有多少个典型用途区间求和、区间修改、区间最值查排名、查第 k 大、统计某个值范围内有多少个数这是一个维护区间最小值的线段树但它的下标不是数组的位置而是数值离散化后的值。比如原数组里有数字{3, 5, 12, 100}离散化后变成{1, 2, 3, 4}。那线段树下标1~4分别对应这些数。在每个下标里我们存的是已经遍历过的、值为该数的那些元素它们的 DP 值的最小值。两个操作update(p, val)告诉线段树值为p的位置我来报到一个值val你帮我取个 min。query(l, r)问线段树在区间[l, r]也就是值在[l, r]范围内的所有元素里最小的 DP 值是多少为什么用线段树因为我们要快速在一段权值区间里找最小值暴力扫是 O(n) 的线段树是 O(logn)。离散化部分vectorlong long vals(a.begin() 1, a.end()); sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); int m vals.size();原数组 ai 的范围是 1∼10e18不能直接当下标用。离散化就是把它们压缩到 1∼mm≤n让线段树开得下。auto get_id [](long long x) { return lower_bound(vals.begin(), vals.end(), x) - vals.begin() 1; };二分查找给我一个数 x告诉我它在离散化数组里的编号从 1 开始方便线段树。pos[i] get_id(a[i]); // a[i] 自己的编号 L[i] get_id(a[i] * 2); // 2*a[i] 的下界编号 R[i] get_end(a[i] * 3 - 1); // 3*a[i] 的上界编号回忆题目要求2ak≤ai≤3ak如果我们正序 DP 找前面的 k。但我们的板子是倒序做的含义反过来找后面的 k满足 2ai≤ak≤3ai。L[i]后面那个数 ak 至少要是 2ai所以在离散化数组里的最小位置。R[i]后面那个数 ak 最多是 3ai所以在离散化数组里的最大位置。也就是说后面所有合法的 k它们的pos[k]一定落在[L[i], R[i]]这个闭区间里。改成别的题时需要动的地方位置改什么L[i] get_id(a[i] * 2)改成下界条件R[i] get_end(a[i] * 3 - 1)改成上界条件seg.query(L[i], R[i])如果要求最大值就换成SegMax相应改min→max、INF→-INFprev[i] i如果 DP 定义变了比如以 i 开头的初始化跟着改suf[l] r判断条件根据你定义的 f 的含义调整