Day 032-Q1 — フラクタル・自己相似構造DP

2026-05-15 赤色 Master / Phase 8+ ★★★★★★★★★ 分割統治 + LIS

問題

長さ $3^K$ のフラクタル数列に対し、更新クエリとフラクタル制約付き LIS クエリ（区間 $[l, r)$、$l, r$ はレベル境界）を処理せよ。

制約

$1 \le K \le 6$（$N \le 729$）
$1 \le Q \le 10^5$
$0 \le V_i \le 10^9$

入出力例

入力例 1

2 3
1 3 2 4 5 1 2 6 3
2 0 9
1 3 7
2 0 9

出力例 1

5
6

ヒント (段階的開示)

ヒント1: 方向性
フラクタル構造の自己相似性を分割統治で活用。
ヒント2: アプローチ
各ブロックで patience sorting テールを管理、ブロック間で出口値を引き継ぐ。
ヒント3: 直接計算
$K \le 6$, $N \le 729$ なので各クエリ $O(N \log N)$ で十分。

模範解答 (Python)

import sys
from bisect import bisect_left

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    def rd():
        nonlocal idx
        v = input_data[idx]; idx += 1
        return v
    K = int(rd()); Q = int(rd())
    V = [int(rd()) for _ in range(3**K)]
    N = 3**K

    def fractal_lis_range(l, r):
        if r - l == 1:
            return 1
        tails = []
        def process(bl, br):
            if br - bl == 1:
                v = V[bl]
                pos = bisect_left(tails, v)
                if pos == len(tails):
                    tails.append(v)
                else:
                    tails[pos] = v
                return
            bs = (br - bl) // 3
            for i in range(3):
                process(bl + i * bs, bl + (i + 1) * bs)
        process(l, r)
        return len(tails)

    for _ in range(Q):
        t = int(rd())
        if t == 1:
            p = int(rd()); x = int(rd())
            V[p] = x
        else:
            l = int(rd()); r = int(rd())
            print(fractal_lis_range(l, r))

main()

Step-by-Step 解説

1フラクタル構造
レベル $k$ ブロック = レベル $k-1$ × 3。ブロック内・ブロック間共に単調増加制約。
2通常 LIS との違い
制約により patience sorting 適用方法が異なる。
3分割統治
各クエリで再帰的に小ブロック処理 → tails に追加。
4更新
点更新は直接 $V[p]$ を書き換え。

よくあるミス

ミス原因正しい書き方
フラクタル制約無視通常 LIS で解く再帰的ブロック構造を保持
K=0 の境界再帰の基底葉では return 1
bisect_left vs right等値の扱い狭義単調増加なら bisect_left

次のステップ

  • 区間更新 + 遅延セグメント木

自己評価

自分の回答

気づき・メモ