問題概要
$N \ $個の整数$ \ a_1,a_2,\ldots,a_N \ $が与えられる。
$A \ $の連続部分列であってそれらの論理積が$ \ K \ $より大きくなるものについて、その部分列の長さの最大値を求めよ。
制約
- $1 \leq N \leq 10^5$
- $0 \leq K \leq 2^{60}$
- $0 \leq a_i \leq 2^{60}$
解説
$f(l,r) = a_l \ \mathrm{AND} \ a_{l+1} \ \mathrm{AND} \ \ldots \ \mathrm{AND} \ a_r \ $とすると、$M \ $は$ \ f(l,r) \gt K \ $を満たす$ \ r - l + 1 \ $の最大値となります。
$l \ $を固定したとき、任意の正整数$ \ k \ $について$ \ f(l,r) \geq f(l,r + k) \ $が自明に成り立ちます。
そのため、各$ \ l \ $について$ \ r \ $を全探索するか、尺取り法により答えを求めることができます。
また、$f(l,r) \ $の値はビットごとに累積和を取っておくか、セグメントツリーを用いて高速に求めることができます。
