Day 049-Q4 — 区間LIS（CDQ分割統治 + patience sorting 前計算）

2026-06-02 赤色 Master / Phase 8+ ★★★★★★★★★ 区間クエリ付き LIS / patience sorting / 前計算テーブル

問題

長さ $N$ の数列 $A_1, A_2, \ldots, A_N$ と $Q$ 個のクエリが与えられる。各クエリ $(l_i, r_i)$ に対して、$A[l_i..r_i]$ の最長増加部分列（LIS）の長さを求めよ。

部分列はインデックスが単調増加かつ値が狭義単調増加のものとする。

制約

$1 \le N \le 3000$
$1 \le Q \le 3000$
$1 \le A_i \le 10^9$
$1 \le l_i \le r_i \le N$
時間制限: 5秒

入出力例

入力例 1

6 3
3 1 4 1 5 9
1 6
1 3
3 6

出力例 1

4
2
3

全体LIS: $[1,4,5,9]$ 長さ4。$A[1..3]=[3,1,4]$ LIS: $[1,4]$ 長さ2。$A[3..6]=[4,1,5,9]$ LIS: $[4,5,9]$ 長さ3

概念図: 左端固定による patience sorting の拡張

左端 l=0 を固定して右端 r を拡張（数列: 3,1,4,1,5,9） r=0: tails=[3] LIS=1 r=1: tails=[1] LIS=1 r=2: tails=[1,4] LIS=2 r=3: tails=[1,4] LIS=2 r=4: tails=[1,4,5] LIS=3 r=5: tails=[1,4,5,9] LIS=4 lis_table[l][r] の前計算テーブル（全左端×右端の組み合わせ） l\r 0 1 2 3 4 5 0 1 1 2 2 3 4 1 - 1 2 2 3 4 2 - - 1 1 2 3 各クエリ (l,r) は O(1) で回答可能

ヒント（段階的開示）

ヒント1: 方向性
各クエリを独立に $O(N \log N)$ で解くと $O(QN \log N)$ となります。$N=Q=3000$ では約 $10^8$ でギリギリです。より効率的な方法として、左端 $l$ を固定して右端 $r$ を拡張するテーブルを事前計算します。
ヒント2: patience sorting の増分更新
左端 $l$ を固定し、$r$ を $l$ から $N-1$ まで増やすとき、$A[r]$ を tails 配列に挿入するだけで $\text{lis\_table}[l][r]$ が更新されます。$O(N \log N)$ で全 $r$ の値を計算できます。
ヒント3: テーブル構築の骨格 
from bisect import bisect_left

lis_table = [[0] * N for _ in range(N)]

for l in range(N):
    tails = []
    for r in range(l, N):
        val = A[r]
        pos = bisect_left(tails, val)
        if pos == len(tails):
            tails.append(val)
        else:
            tails[pos] = val
        lis_table[l][r] = len(tails)

# クエリ (l, r) の回答: lis_table[l-1][r-1]

模範解答 (Python)

import sys
from bisect import bisect_left

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N, Q = int(data[idx]), int(data[idx+1]); idx += 2
    A = [int(data[idx+i]) for i in range(N)]; idx += N

    # Precompute lis_table[l][r] = LIS of A[l..r]  (0-indexed)
    # O(N^2 log N) time, O(N^2) space
    lis_table = [[0] * N for _ in range(N)]

    for l in range(N):
        tails = []
        for r in range(l, N):
            val = A[r]
            pos = bisect_left(tails, val)
            if pos == len(tails):
                tails.append(val)
            else:
                tails[pos] = val
            lis_table[l][r] = len(tails)

    out = []
    for _ in range(Q):
        l, r = int(data[idx]) - 1, int(data[idx+1]) - 1; idx += 2
        out.append(lis_table[l][r])

    sys.stdout.write('\n'.join(map(str, out)) + '\n')

solve()

Step-by-Step 解説

1patience sorting によるLIS
配列 $A$ の LIS 長さを求めるには patience sorting（二分探索 + tails 配列）が使えます。$A[r]$ を tails の適切な位置に挿入（または追加）し、tails の長さが LIS の長さになります。
2左端固定・右端拡張
左端 $l$ を固定して右端 $r$ を増やすとき、新しい要素 $A[r]$ を tails に追加するだけで $\text{lis\_table}[l][r]$ が得られます。$l$ を一つ変えるたびに tails を初期化し直します。
3テーブルのメモリ
$N=3000$ では $9 \times 10^6$ 要素のテーブルが必要です。Python の `int` は大きいため、`array.array('H', ...)` や numpy を使うとメモリを節約できます。
4クエリへの回答
前計算後は各クエリを $O(1)$ で回答できます。1-indexed から 0-indexed に変換して `lis_table[l-1][r-1]` を返します。
5計算量
前計算: $O(N^2 \log N)$。クエリ: $O(Q)$。$N=3000$ では約 $3000^2 \times 12 \approx 10^8$ で制限内。

計算量

前計算: $O(N^2 \log N)$
各クエリ: $O(1)$
全体: $O(N^2 \log N + Q)$
空間: $O(N^2)$（テーブル）

よくあるミス

ミス原因正しい書き方
tails をループ間でリセットしないl が変わる際に前の tails が残るl ループの先頭で tails = []
狭義 vs 広義 LISbisect_left vs bisect_right狭義増加なら bisect_left
1-indexed と 0-indexed の混同クエリが 1-indexedl-1, r-1 に変換
メモリ不足N=3000 で N^2 テーブルarray.array('H', ...) で節約

次のステップ

  • 発展問題: 3次元 LIS（インデックス・値・色の3条件）を CDQ で $O(N \log^2 N)$
  • 関連: Day034 Q2（3D LIS + CDQ）の復習
  • 応用: 区間 LIS を使った問題（区間マージ最長共通部分列等）

自己評価