在值域上用树状数组维护可合并信息 (长度, 方案数),合并时长度大者胜、等长则方案数相加,空段记为 1 种方案,O(n log n) 求出最长严格上升子序列长度与方案数。
OJ: roj
题目 ID: 1742
难度:提高+/省选-
标签:动态规划树状数组计数python
创建: 2026-10-07 20:41
更新: 2026-10-07 20:41
形式化题目
给定长度为
要求出
即最长严格上升子序列的长度;若
计数口径:按下标位置计数——两条子序列只要选中的下标集合不同就算两种方案,
因此同一个电阻值出现在不同位置时互不合并。这可以由数据反推确认:problem4
(10 9 8 7 6 5 4 3 2 1,
数据范围:
正解
思路
先解决"长度"。 设
直接按这个式子做是
麻烦在于还要数方案。 长度和方案数是两个量,但它们可以打包成一个整体一起维护: 对值域的任意一段区间,定义它携带的信息为
其中
两段区间的信息怎么合并? 定义
也就是说:长度大者胜;长度相等时方案数相加。这正符合"最长上升子序列的方案数"的定义—— 只有恰好达到最大长度的方案才被计入,短于最大长度的方案不能混进来。
空段的哨兵必须是
这个合并满足结合律,可以用树状数组。 不难逐例验证
- 把电阻值离散化成
,则"取值严格小于 "等价于" "; - 从左往右扫
:先查前缀 得到最优前缀信息,令 , 再把 合并进位置 ; - 全部扫完后,整个值域
的合并结果就是全局答案 。
为什么查询的是 problem4 会输出
以题目样例 dp 是当前位置贡献的信息,值域状态 只列出已更新过的 rank):
| 查询前缀 |
更新后的值域关键状态 | ||||
|---|---|---|---|---|---|
| 1 | 1 | 1 | rank1 |
||
| 2 | 3 | 3 | rank1 |
||
| 3 | 2 | 2 | rank2 |
||
| 4 | 5 | 5 | rank5 |
||
| 5 | 4 | 4 | rank4 |
最后一次全局合并把 rank4 的
边界与实现要点。
,因此答案长度至少为 ; 时只打印一行,不要多输出空行。 - 方案数只在
上取模, 是真实长度、绝不取模。 - 值域离散化后
,BIT 开 大小即可,不依赖"电阻值 "这个上界。 - 合并函数在等长相加时要做
if (c >= MOD) c -= MOD,避免多次加法溢出(两数都小于,一次减法足够)。
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 20:41
# update_at: 2026-10-07 20:41
import sys
MOD = 123456789 # 题目要求的方案数模数
EMPTY = (0, 1) # 值域空段的信息:长度 0 表示“一条都不选”,方案数恒为 1(单位元)
# 值域上的可合并信息 (最长严格上升子序列长度, 该长度下的方案数)
type Info = tuple[int, int]
def merge_info(x: Info, y: Info) -> Info:
"""合并两段值域信息:长度大者胜;等长则方案数相加;两段皆空时方案数仍为 1。"""
(len_x, cnt_x), (len_y, cnt_y) = x, y
if len_y > len_x:
return y
if len_y == len_x and len_x > 0: # 都是空段时不能把 1 加两次
return (len_x, (cnt_x + cnt_y) % MOD)
return x
def prefix_best(bit_len: list[int], bit_cnt: list[int], pos: int) -> Info:
"""值域前缀 [1, pos] 的合并信息,即取值落在该前缀内的最优子序列信息。"""
best: Info = EMPTY
while pos > 0:
best = merge_info(best, (bit_len[pos], bit_cnt[pos]))
pos -= pos & -pos # BIT 前缀拆分
return best
def insert(bit_len: list[int], bit_cnt: list[int], pos: int, info: Info) -> None:
"""把 info 合并进值域位置 pos,维护 BIT 各节点覆盖区间的合并结果。"""
size = len(bit_len)
while pos < size:
bit_len[pos], bit_cnt[pos] = merge_info((bit_len[pos], bit_cnt[pos]), info)
pos += pos & -pos # BIT 单点合并的影响链
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, type_ = next(data), next(data)
resist = [next(data) for _ in range(n)]
rank = {v: i for i, v in enumerate(sorted(set(resist)), 1)} # 离散化:电阻值 -> rank
k = len(rank)
bit_len, bit_cnt = [0] * (k + 1), [1] * (k + 1) # 初始全是空段
for v in resist:
r = rank[v]
best_len, best_cnt = prefix_best(bit_len, bit_cnt, r - 1) # 严格小于 v 的部分
insert(bit_len, bit_cnt, r, (best_len + 1, best_cnt)) # 以 v 结尾接在最优前缀后
ans_len, ans_cnt = prefix_best(bit_len, bit_cnt, k) # 整个值域合并 = 全局答案
out = [str(ans_len)]
if type_ == 1:
out.append(str(ans_cnt))
print('\n'.join(out))
if __name__ == "__main__":
solve()C++ 版(同一算法):
// 1742 导线问题
// 一本通 · 高手训练篇(四、数据结构)—— 与经典题「降雷皇」题面一致
//
// 题意:给定长度 n 的序列 a[1..n],求最长严格上升子序列的长度 L;
// 若 type=1,再输出长度恰为 L 的严格上升子序列个数(按“下标位置”计数,
// 同一数值出现在不同位置视为不同方案),答案对 123456789 取模。
//
// 算法:树状数组(BIT)维护值域上的可合并信息 (len, cnt)
// dp[i] = 以 i 结尾的最优信息 = merge(值域上「严格小于 a[i]」的前缀) 再 (len+1)
// 合并规则:len 大者胜;len 相等时 cnt 相加(取模);两侧都是空序列(len==0)
// 时代表“一条都不选”,方案数为 1(哨兵/单位元)。
// 该合并满足结合律、交换律且以 (0,1) 为单位元,故 BIT 前缀查询正确。
// 值域先离散化,严格上升 ⇔ 查询 rank-1 的前缀。
//
// 复杂度:时间 O(n log n),空间 O(n)。
//
// 编译:/opt/homebrew/bin/g++-16 -O2 -std=c++17 -o main main.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 123456789; // 题目要求的模数
const int MAXN = 100005; // n 的上限
int n, type_;
int a[MAXN]; // 原序列
int val[MAXN]; // 离散化用的有序去重值
int bitLen[MAXN]; // 值域 BIT:最长长度
int bitCnt[MAXN]; // 值域 BIT:该长度下的方案数
// 合并两段值域信息:长度大者胜,长度相等则方案数相加
// 特判:两侧长度都为 0 表示区间为空,方案数保持 1
inline void mergeInto(int &len, int &cnt, int l2, int c2) {
if (l2 > len) {
len = l2;
cnt = c2;
} else if (l2 == len && len > 0) {
cnt += c2;
if (cnt >= MOD) cnt -= MOD;
}
}
int main() {
scanf("%d %d", &n, &type_);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
val[i] = a[i];
}
// 离散化:rank ∈ [1, K]
sort(val + 1, val + n + 1);
int K = (int)(unique(val + 1, val + n + 1) - val - 1);
// BIT 初始化:每个位置都是“空序列”,长度 0、方案数 1
for (int i = 1; i <= K; i++) {
bitLen[i] = 0;
bitCnt[i] = 1;
}
for (int i = 1; i <= n; i++) {
int r = (int)(lower_bound(val + 1, val + K + 1, a[i]) - val); // 当前值的 rank
// 查询取值严格小于 a[i] 的部分(rank ∈ [1, r-1])
int bestLen = 0, bestCnt = 1;
for (int j = r - 1; j > 0; j -= j & (-j)) {
mergeInto(bestLen, bestCnt, bitLen[j], bitCnt[j]);
}
// 接在最优前缀后面,构成以 i 结尾的上升子序列
int curLen = bestLen + 1;
int curCnt = bestCnt;
// 把 dp[i] 合并进值域位置 r
for (int j = r; j <= K; j += j & (-j)) {
mergeInto(bitLen[j], bitCnt[j], curLen, curCnt);
}
}
// 全局答案 = 整个值域前缀 [1, K] 的合并结果
int ansLen = 0, ansCnt = 1;
for (int j = K; j > 0; j -= j & (-j)) {
mergeInto(ansLen, ansCnt, bitLen[j], bitCnt[j]);
}
printf("%d\n", ansLen);
if (type_ == 1) printf("%d\n", ansCnt);
return 0;
}复杂度
- 时间:离散化排序
;每个位置做一次前缀查询与一次单点合并,各 , 合并是与规模无关的常数次运算。总计 。 时约 次合并,C++ 实测远低于 1000 ms 的限制。 - 空间:原序列、离散化数组与两个 BIT 数组,各
,总计 ,约 MB。 - 与 C++ 解法的关系:
main.py与main.cpp是同一算法的两种落地——值域离散化 + 树状数组维护的合并信息,复杂度同为 。 Python 侧多出的是常数(每次合并要构造 tuple),在 的极限数据上会明显慢于 C++,但算法没有降级,属于该题允许的 Python TLE 风险。
总结
- 计数型 DP 的关键是把"长度"和"方案数"打包成一个可合并的信息,并写对合并规则: 长度大者胜、等长相加;这样前缀查询可以直接用树状数组,而不需要为"最优值的个数"另建结构。
- 单位元必须与"空"的语义一致。空段代表"一条都不选",方案数是
而不是 , 并且两个空段合并时要特判,否则哨兵会被反复累加。 - 严格上升 ⇔ 查询
的前缀,离散化后所有相等值共享同一个 rank, 这一步写错会在含重复值的数据上直接翻车。 - 长度不取模、只对方案数取模;
时只输出一行。 - 关于数据的说明:本仓库素材源中附带了数据生成脚本(
data.py)与配置, 说明data/是自造的、题面也可能是按公开题解重建的(本题与经典题「降雷皇」题面一致), 出题意图与官方原题可能存在偏差;上文所有结论均以随仓data/的.out实测对齐为准, 其中"按位置计数"的口径是由problem4、problem10两个点反推确认的。