Day 040-Q3 — LIS 経路数え上げ（BIT + 座標圧縮）

2026-05-23 赤色 Master / Phase 8+ ★★★★★★★★★ LIS Count + (max,count) BIT

問題

長さ $N$ の整数列 $A$ に対して以下を求めよ：

  1. 最長増加部分列（LIS）の長さ $L$
  2. 長さ $L$ の増加部分列の個数（$\bmod 998244353$）

制約

$1 \le N \le 2 \times 10^5$
$1 \le A_i \le 10^9$
時間制限: 3sec / メモリ: 256MB

入出力例

入力例 1

6
3 1 4 1 5 9

出力例 1

4
2

入力例 2

5
1 3 2 4 5

出力例 2

4
3

概念図: (max, count) BIT の動作

A = [3, 1, 4, 1, 5, 9]、座標圧縮: {1→1, 3→2, 4→3, 5→4, 9→5} A[i] rank query(rank-1) dp[i] cnt[i] 備考 3 2 (0, 0) 1 1 初期要素 1 1 (0, 0) 1 1 初期要素 4 3 (1, 2) 2 2 1,3 の両方から 1 1 (0, 0) 1 1 重複値 5 4 (2, 2) 3 2 [1,4]と[3,4]から 9 5 (3, 2) 4 2 LIS長=4, 個数=2 LIS = [1,4,5,9] と [3,4,5,9] の 2 通り BIT クエリで「rank < 現在のrank で最大 dp 値とその個数」を O(log N) で取得

ヒント（段階的開示）

ヒント1: 方向性
LIS の長さは patience sorting + 二分探索で O(N log N)。個数の数え上げも同様の DP で管理できる。各要素について「自分で終わる LIS の長さ」と「その個数」を求める。
ヒント2: (max, count) BIT
座標圧縮 + BIT で「A[j] < A[i] の中で dp[j] が最大のものの cnt 合計」を O(log N) で求める。BIT の各インデックスには (max_len, count) ペアを保持し、クエリ時に同 max_len なら count を合算。
ヒント3: 実装骨格 
class BIT:
    def query(self, i):
        """1..i の (max_len, count)"""
        ml, mc = 0, 0
        while i > 0:
            if self.len_[i] > ml: ml, mc = self.len_[i], self.cnt[i]
            elif self.len_[i] == ml: mc += self.cnt[i]
            i -= i & (-i)
        return ml, mc % MOD

    def update(self, i, l, c):
        while i <= self.n:
            if l > self.len_[i]: self.len_[i], self.cnt[i] = l, c
            elif l == self.len_[i]: self.cnt[i] = (self.cnt[i] + c) % MOD
            i += i & (-i)

模範解答 (Python)

import sys
input = sys.stdin.readline
MOD = 998244353

class BIT:
    def __init__(self, n):
        self.n = n
        self.len_ = [0] * (n+1)
        self.cnt = [0] * (n+1)

    def query(self, i):
        ml, mc = 0, 0
        while i > 0:
            if self.len_[i] > ml:
                ml = self.len_[i]
                mc = self.cnt[i]
            elif self.len_[i] == ml:
                mc = (mc + self.cnt[i]) % MOD
            i -= i & (-i)
        return ml, mc

    def update(self, i, l, c):
        while i <= self.n:
            if l > self.len_[i]:
                self.len_[i] = l
                self.cnt[i] = c
            elif l == self.len_[i]:
                self.cnt[i] = (self.cnt[i] + c) % MOD
            i += i & (-i)

def solve():
    N = int(input())
    A = list(map(int, input().split()))

    sorted_unique = sorted(set(A))
    rank = {v: i+1 for i, v in enumerate(sorted_unique)}
    M = len(sorted_unique)

    bit = BIT(M)
    dp = [0] * N
    cnt = [0] * N

    for i in range(N):
        r = rank[A[i]]
        ml, mc = bit.query(r - 1)
        dp[i] = ml + 1
        cnt[i] = mc if mc > 0 else 1
        bit.update(r, dp[i], cnt[i])

    L = max(dp)
    total = 0
    for i in range(N):
        if dp[i] == L:
            total = (total + cnt[i]) % MOD

    print(L)
    print(total)

solve()

Step-by-Step 解説

1問題の分解
LIS の長さ L は O(N log N) で求まる（patience sorting）。個数を求めるには各要素で終わる LIS の本数を DP で管理する。
2DP 定義
dp[i] = A[i] で終わる LIS の長さ。cnt[i] = そのような LIS の個数 mod p。遷移には「A[j] < A[i] かつ dp[j] が最大」の情報が必要。
3座標圧縮
A の値を 1-indexed のランクに変換。BIT のインデックスとして使用。
4(max, count) BIT の実装
通常の BIT は加算ベースだが、(max_len, count) ペアを管理する特殊実装が必要。update 時：同じ長さなら count を加算、長い場合は置き換え。
5最終集計
dp[i] == L となる全 cnt[i] の総和が答え。

計算量

座標圧縮: $O(N \log N)$
各要素の BIT クエリ + 更新: $O(\log N)$ per element
全体: $O(N \log N)$
メモリ: $O(N)$

よくあるミス

ミス原因正しい書き方
cnt の初期値mc=0 のとき（最初の要素）は cnt=1cnt[i] = mc if mc > 0 else 1
BIT の update で同長を加算しない同じ長さ達成の複数経路を見逃すlen_[i] == l のとき cnt += c
座標圧縮で rank を 0-indexed にするBIT が 1-indexedrank = {v: i+1 for i, v in ...}
query(r) とすべきを query(r-1) にするA[i] 自身を含めてしまうbit.query(r - 1) で strictly less

次のステップ

  • 発展: 最長非増加部分列（LNDS）
  • 応用: 2次元 LIS（(x,y) 対で x も y も増加）= CDQ 分割統治
  • 類題: LIS を $K$ 本非重複で選ぶ（Dilworth 定理 + フロー）

自己評価