导线问题

GitHub跳转原题关系图返回列表

在值域上用树状数组维护可合并信息 (长度, 方案数),合并时长度大者胜、等长则方案数相加,空段记为 1 种方案,O(n log n) 求出最长严格上升子序列长度与方案数。

OJ: roj

题目 ID: 1742

难度:提高+/省选-

标签:动态规划树状数组计数python

创建: 2026-10-07 20:41

更新: 2026-10-07 20:41

形式化题目

给定长度为 nn 的整数序列 a1,a2,…,ana_1, a_2, \dots, a_n(aia_i 是第 ii 条导线的电阻值)和一个类型标记 type\texttt{type}。电光从一根导线传到另一根导线,当且仅当后者电阻值严格更大且下标在右侧, 中间可以跳过任意多根导线。于是"电光经过的一串导线"就是原序列的一个严格上升子序列。

要求出

L=max⁡{ k:∃ i1<i2<⋯<ik,  ai1<ai2<⋯<aik }, L = \max\{\,k : \exists\, i_1 < i_2 < \cdots < i_k,\; a_{i_1} < a_{i_2} < \cdots < a_{i_k}\,\},

即最长严格上升子序列的长度;若 type=1\texttt{type} = 1,还要输出长度恰为 LL 的严格上升子序列 个数对 123456789123456789 取模的值。

计数口径:按下标位置计数——两条子序列只要选中的下标集合不同就算两种方案, 因此同一个电阻值出现在不同位置时互不合并。这可以由数据反推确认:problem4 (10 9 8 7 6 5 4 3 2 1,L=1L = 1)的答案是 1010 而不是 11,即每个位置各算一种方案。

数据范围:n⩽100000n \leqslant 100000,电阻值不超过 100000100000,时间限制 1000 ms、空间限制 256 MB。 当 type=0\texttt{type} = 0 时只需输出第一行的长度。

正解

思路

先解决"长度"。 设 fif_i 为以第 ii 根导线结尾的最长严格上升子序列长度,则

fi=1+max⁡({0}∪{fj:j<i,  aj<ai}),L=max⁡ifi. f_i = 1 + \max\big(\{0\} \cup \{f_j : j < i,\; a_j < a_i\}\big), \qquad L = \max_i f_i .

直接按这个式子做是 O(n2)O(n^2) 的。两个维度(下标在左、取值更小)里,下标维度天然被"从左往右 扫描"消掉了,剩下要问的只是一个值域上的前缀最大值:扫到 ii 时,需要的是 “取值严格小于 aia_i 的那些已处理位置中最优的信息”。把值域离散化后,这就是一个 单点更新、前缀查询的问题,用树状数组或线段树都能做到 O(nlog⁡n)O(n \log n)。

麻烦在于还要数方案。 长度和方案数是两个量,但它们可以打包成一个整体一起维护: 对值域的任意一段区间,定义它携带的信息为

info=(len, cnt), \text{info} = (\text{len},\ \text{cnt}) ,

其中 len\text{len} 是"取该区间内的值作为结尾能接到的最长上升子序列长度",cnt\text{cnt} 是达到 该长度的方案数。于是 dpidp_i 就是"取值严格小于 aia_i 的那段前缀的 info"再令长度 +1+1:

dpi=(len前缀+1, cnt前缀). dp_i = (\text{len}_{\text{前缀}} + 1,\ \text{cnt}_{\text{前缀}}) .

两段区间的信息怎么合并? 定义

merge((l1,c1),(l2,c2))={(l2,c2),l2>l1,(l1,(c1+c2) mod 123456789),l1=l2 且 l1>0,(l1,c1),l1>l2. \text{merge}\big((l_1, c_1), (l_2, c_2)\big) = \begin{cases} (l_2, c_2), & l_2 > l_1, \\[2pt] (l_1, (c_1 + c_2) \bmod 123456789), & l_1 = l_2 \text{ 且 } l_1 > 0, \\[2pt] (l_1, c_1), & l_1 > l_2 . \end{cases}

也就是说:长度大者胜;长度相等时方案数相加。这正符合"最长上升子序列的方案数"的定义—— 只有恰好达到最大长度的方案才被计入,短于最大长度的方案不能混进来。

空段的哨兵必须是 (0,1)(0, 1) 而不是 (0,0)(0, 0)。 值域上一段还没被任何位置"到达"过的区间, 其含义是"一条导线都不选",这本身就是唯一一种方案。若把空段写成 (0,0)(0, 0), 那么"从零开始"的 dpidp_i 会得到 c=0c = 0,长度为 11 的子序列方案数就丢了。 反过来,两个空段合并时如果按"等长相加"处理就会变成 (0,2)(0, 2),所以合并函数里必须特判 l1=l2=0l_1 = l_2 = 0 的情形,直接返回哨兵 (0,1)(0, 1)。

这个合并满足结合律,可以用树状数组。 不难逐例验证 merge\text{merge} 可交换、可结合, 且以 (0,1)(0,1) 为单位元;树状数组的前缀查询只需要结合律(不需要逆元), 所以把每个 BIT 节点存成"它覆盖的那段值域的合并结果"就能正确回答任意前缀查询。 做法是:

  1. 把电阻值离散化成 rank∈[1,K]\text{rank} \in [1, K],则"取值严格小于 aia_i"等价于"rank∈[1,rank(ai)−1]\text{rank} \in [1, \text{rank}(a_i) - 1]";
  2. 从左往右扫 ii:先查前缀 [1,rank(ai)−1][1, \text{rank}(a_i) - 1] 得到最优前缀信息,令 dpi=(len+1,cnt)dp_i = (\text{len}+1, \text{cnt}), 再把 dpidp_i 合并进位置 rank(ai)\text{rank}(a_i);
  3. 全部扫完后,整个值域 [1,K][1, K] 的合并结果就是全局答案 (ansLen,ansCnt)(\text{ansLen}, \text{ansCnt})。

为什么查询的是 rank−1\text{rank} - 1? 因为要求严格上升:与 aia_i 取值相同的位置不能接在它前面, 而离散化后所有等于 aia_i 的值都落在同一个 rank\text{rank} 上,所以前缀必须扣掉这一档。 这也是本题最容易写错的地方——若写成查询 [1,rank(ai)][1, \text{rank}(a_i)],重复值就会被误接上去, problem4 会输出 L=10L = 10 而不是 11。

以题目样例 a=(1,3,2,5,4)a = (1, 3, 2, 5, 4) 为例,离散化后值域为 {1,2,3,4,5}\{1, 2, 3, 4, 5\}, 逐位置追踪如下(dp 是当前位置贡献的信息,值域状态 只列出已更新过的 rank):

ii aia_i rank\text{rank} 查询前缀 [1,rank−1][1, \text{rank}-1] dpidp_i 更新后的值域关键状态
1 1 1 (0,1)(0, 1)(空) (1,1)(1, 1) rank1 (1,1)(1,1)
2 3 3 (1,1)(1, 1) (2,1)(2, 1) rank1 (1,1)(1,1),rank3 (2,1)(2,1)
3 2 2 (1,1)(1, 1) (2,1)(2, 1) rank2 (2,1)(2,1)
4 5 5 (2,2)(2, 2)(rank2 与 rank3 等长相加) (3,2)(3, 2) rank5 (3,2)(3,2)
5 4 4 (2,2)(2, 2) (3,2)(3, 2) rank4 (3,2)(3,2)

最后一次全局合并把 rank4 的 (3,2)(3,2) 与 rank5 的 (3,2)(3,2) 相加,得到 (3,4)(3, 4): 长度 33,方案数 44(分别是 1 3 51\,3\,5、1 3 41\,3\,4、1 2 51\,2\,5、1 2 41\,2\,4),与样例输出一致。

边界与实现要点。

  • n⩾1n \geqslant 1,因此答案长度至少为 11;type=0type = 0 时只打印一行,不要多输出空行。
  • 方案数只在 cnt\text{cnt} 上取模,len\text{len} 是真实长度、绝不取模。
  • 值域离散化后 K⩽nK \leqslant n,BIT 开 K+1K + 1 大小即可,不依赖"电阻值 ⩽100000\leqslant 100000"这个上界。
  • 合并函数在等长相加时要做 if (c >= MOD) c -= MOD,避免多次加法溢出(两数都小于 MODMOD,一次减法足够)。

代码

Python 版:

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++ 版(同一算法):

cpp
// 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;
}

复杂度

  • 时间:离散化排序 O(nlog⁡n)O(n \log n);每个位置做一次前缀查询与一次单点合并,各 O(log⁡K)O(\log K), 合并是与规模无关的常数次运算。总计 O(nlog⁡n)O(n \log n)。 n=105n = 10^5 时约 3.4×1063.4 \times 10^6 次合并,C++ 实测远低于 1000 ms 的限制。
  • 空间:原序列、离散化数组与两个 BIT 数组,各 O(n)O(n),总计 O(n)O(n),约 1.61.6 MB。
  • 与 C++ 解法的关系:main.py 与 main.cpp 是同一算法的两种落地——值域离散化 + 树状数组维护 (len,cnt)(\text{len}, \text{cnt}) 的合并信息,复杂度同为 O(nlog⁡n)O(n \log n)。 Python 侧多出的是常数(每次合并要构造 tuple),在 n=105n = 10^5 的极限数据上会明显慢于 C++,但算法没有降级,属于该题允许的 Python TLE 风险。

总结

  • 计数型 DP 的关键是把"长度"和"方案数"打包成一个可合并的信息,并写对合并规则: 长度大者胜、等长相加;这样前缀查询可以直接用树状数组,而不需要为"最优值的个数"另建结构。
  • 单位元必须与"空"的语义一致。空段代表"一条都不选",方案数是 11 而不是 00, 并且两个空段合并时要特判,否则哨兵会被反复累加。
  • 严格上升 ⇔ 查询 rank−1\text{rank} - 1 的前缀,离散化后所有相等值共享同一个 rank, 这一步写错会在含重复值的数据上直接翻车。
  • 长度不取模、只对方案数取模;type=0type = 0 时只输出一行。
  • 关于数据的说明:本仓库素材源中附带了数据生成脚本(data.py)与配置, 说明 data/ 是自造的、题面也可能是按公开题解重建的(本题与经典题「降雷皇」题面一致), 出题意图与官方原题可能存在偏差;上文所有结论均以随仓 data/ 的 .out 实测对齐为准, 其中"按位置计数"的口径是由 problem4、problem10 两个点反推确认的。