CF競賽題目講解_CF474E(樹狀數(shù)組)
2022-08-04 10:53 作者:Clayton_Zhou | 我要投稿
// https://codeforces.com/problemset/problem/474/e
因為 a 范圍很大，所以先排序去重到 b 數(shù)組。
令 dp[i] 表示取到了第 i 個數(shù)的最大長度。
然后在 b 中二分找到大于等于 hi+d 的第一個位置r，二分找到小于等于 hi?d 的第一個位置 l。
隨后需要知道 hi 在區(qū)間 [1,l] 或 [r,upper_limit] 內(nèi)的 max{dp[res]}。
這里使用2個樹狀數(shù)組維護(hù)最大值
input
5 2
1 3 6 7 4
標(biāo)簽：
