ACLBC D - Flat Subsequence (400)
$ dp[i
]をi番目を最後としたときの最長の長さとすると、i-1番目の要素までで隣り合う条件を満たす中で一番大きい値に1加えたものになる
これは愚直に求めると
$ O(N^2)
になるが、
$ A_i
の値毎にセグ木に載せることで
$ O(N \log \max A)
になる。
$ A_i
は高々
$ 3 \times 10^5
なので問題ない
範囲を求める際に両端が0未満になったり
$ 3 \times 10^5
を越えたりしないように注意が必要
問題:
https://atcoder.jp/contests/abl/tasks/abl_d
提出:
https://atcoder.jp/contests/abl/submissions/17102168
#ACLBC
#400pt
#D
#AtCoder