一、用倍增替代二分
从高位到低位 枚举 \(2^{k}, 2^{k - 1}, \dots, 1\),\(k\) 自己定,如果能对答案产生贡献并且依然 check() = true
,就加上贡献。
其实很类似于倍增 LCA,只不过某时候用这种方法感觉常数会小一些。
二、实际应用
给定一个数列 \(a_{1}, a_{2}, \dots, a_{n}\),给定 \(k\),求第一个大于 \(k\) 的数的下标,保证 \(\displaystyle \max_{i = 1}^{n} a_i > k\)。
设答案为 \(cur = 0\),从高位到低位(比如 \(2^{19}, 2^{18}, \dots, 2^0\)),如果 \(\displaystyle \max_{i = 1}^{cur + 2^x} a_i \leq k\),就 \(cur + 2^x \to cur\),最终答案就是 \(cur + 1\)。
标签:二分,dots,cur,max,倍增,替代,displaystyle From: https://www.cnblogs.com/RB16B/p/17401951.html