Flat Subsequence (Segment Tree DP) — Animation

DP rule: for each a, query max over values in [a−K, a+K], then update value a to r+1.

Hints

Hint 1

Coordinate compression: sort unique values and map each value to an index. Leaves correspond to these indices.

Hint 2

Node stores max dp over its segment. Merge is max(left,right).

Hint 3

For each a, query over value-range [a−K, a+K] on the compressed index line to get r.

Hint 4

Update the leaf for a with r+1, then pull parents by merge. Global answer is max leaf/internal value seen.

Merge Logic

Node value = max dp in its segment
merge(u) = max(left(u), right(u))
query([L,R]) = max over covered nodes
update(value=a, new=r+1) then pull parents with merge

Array:

Flat Subsequence (Segment Tree DP) — Animation

Hints

Merge Logic

1. Input Array

2. Coordinate Compression

3. Segment Tree (stores max dp)