考察
各クエリは部分配列 [L,R] 内の 0/1 ナップサックで、容量 C は小さい。区間ごとに DP を作ると重複が大きいが、分割点をまたぐクエリは左右の DP を合成できる。
採用する候補: 配列を分割統治し、各節点で中央をまたぐ全クエリへ左 suffix DP と右 prefix DP を構築して答える。
各要素は深さごとに一度 DP 更新へ寄与し、各クエリも一節点で処理されるため O(K(N log N+Q)) になる。
棄却する候補: クエリごとに [L,R] の全アイテムでナップサック DP をやり直す。
区間の重複を共有できず O(NKQ) に達する。
区間 [l,r] の中央 m に対し、L<m≤R のクエリだけをこの節点で処理し、片側に収まるものは再帰へ送る。
容量 j を左に、C-j を右に配る全分割を試せば、左右で独立に選んだ最適値の和が区間全体の最適値になる。
solve(l,r) で m を定め、i=m-1…l の suffix ナップサック dp_l[i][j] と i=m…r の prefix ナップサック dp_r[i][j] を容量 K まで作る。中央をまたぐ各クエリを max_j(dp_l[L][j]+dp_r[R][C-j]) で答え、残りを左右へ再帰する。
空の品物集合の「容量j以下」DPは全jで0に初期化する。品物追加は容量降順でdp[j]=max(dp[j],dp[j−W]+V)。再帰の葉l=rでは、その一品だけを見てW_l≤CならV_l、そうでなければ0と答える。これでL=Rのqueryも必ず処理される。
典型の発動条件
オフライン区間分割統治
発動条件: 静的配列上の多数の区間クエリを、中央をまたぐものと片側のものへ分類できるとき。
各クエリを両端が初めて分かれる節点で一度だけ処理する。
prefix・suffix ナップサック DP
発動条件: 区間が固定境界をまたぎ、左右の選択が容量配分だけで結合するとき。
中央から外向きにアイテムを追加した DP を全端点分共有する。
問題固有の要素
クエリ区間そのものではなく、再帰木で両端が分離する唯一の節点を担当箇所にすると DP の再利用範囲が最大化する。
別の問題へ持ち帰る視点: 結合条件が小さい容量だけなら、左右の区間情報を容量配分の max-plus 畳み込みで合成できる。
正当性
各照会は両端が初めて左右に分かれる節点、または一要素の葉で一度だけ処理される。交差区間の任意の選択は左右の選択に分かれ、容量配分のどれかで必ず表せる。逆に左右のDPの合成は合法な選択なので、その最大が区間の最適値になる。
実装上の注意
- 左 DP は m-1 から降順、右 DP は m から昇順にコピー更新する。容量以下の最大値として j=0 を 0 に初期化し、到達不能値の扱いを統一する。
復習の核
- 中央をまたぐ条件を L<m≤R と統一し、各クエリがちょうど一つの再帰節点で回答されることを確認する。
計算量と制約
時間
O(NK log N+QK)、N品数K最大容量Q区間query。
空間
O(NK+Q)、親配列を解放してから子へ再帰する。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1\leq N \leq 2\times 10^4; 1\leq Q \leq 2\times 10^5; 1\leq W_i \leq 500; 1\leq V_i \leq 10^9; 1\leq L_j \leq R_j \leq N; 1\leq C_j \leq 500; All input values are integers.
出典