atcoder.jp
問題
- 長さNの数列が与えられるよ
- Aの部分列で、かつ、隣接する2項の差の絶対値がD以下であるものを作って欲しい
- 条件を満たす部分列のうち、一番長いものの長さを教えて！
成約
- $1 \leq N \leq 5 \times10^{5}$
- $0 \leq D \leq 5 \times10^{5}$
- $1 \leq A_{i} \leq 5 \times10^{5}$
思考
- DPっぽい雰囲気を感じる
- とりあえず手書きで入力例1のお絵かき
- 最初の3は…一旦採用するとして話を進めて…
- 次の5は、差が2なので採用できる…けど…採用は、したくない、けど…
- とりあえず、数列末尾の数字がわかってれば、新しい$A$を見た時に採用できる/できないが決まるね…？
- 採用/不採用を判断してるから、やっぱりナップザックDP感ある
- じゃあ…DPテーブルを考えて…
- dp[i] := 数列の末尾がiの時の、数列の長さ
- next_dp[i] = max(prev_dp[i-D], prev_dp[i-D+1], ... , prev_dp[i+D]) + 1
- 貰うDPで更新…したところで、結局$O(N^{2})$溶かすのは良くない
- 区間の最大値がパパッとわかってくれたら、とても、嬉しい…
- あ、区間最大値。セグ木でいいのか
- セグ木1本植えて、区間最大値+1を、Aの所に入れていけば、良いのか
コード
from atcoder.segtree import SegTree
N,D = map(int,input().split())
A_L = list(map(int, input().split()))
max_a = max(A_L)
ST = SegTree(max, 0, [0]*(max_a+1))
for a in A_L:
tmp = ST.prod(max(a-D,1),min(a+D,max_a)+1)
ST.set(a,tmp+1)
print(ST.all_prod())
