B - Dividing Subsequence ARC133
問題
順列P, Qが与えられるときに、連続するとは限らない部分列P', Q'を長さKで取る
任意のiについて、Q'i がP'iの倍数になっているとするとあり得る最大のKは何か
解答
全てのiについて、Piに対して同時に選べるQjの組の合計の合計は調和級数より
O(N log N log N)で抑えられる
よって、区間maxのセグ木で
iについてPを捜査していき
seg[j]:=QについてQjを最後に選んだ時の最大の長さとして
インラインでdpを更新していけばいい
具体的には
今見ているiについてjを選べる時に
seg[j] = seg(0, j) + 1
iについてjを右から更新していかないと、同じiについての結果が影響を及ぼすので注意