\(f(l,r)=A_{l} \text{ or } A_{l+1} \text{ or } \cdots \text{ or } A_{r}\)とします。

整数\(x\)を固定した時に、「\(f(l,r)\geq x\)を満たす\((l,r)\)の組は\(K\)組以上あるか？」という判定問題が高速に解ければ、元の問題も二分探索により解くことができます。以後この判定問題を解く方法について考えます。

ここで、\(l\)を固定すると、\(\text{or}\)の性質より、\(f(l,l)\leq f(l,l+1)\leq \cdots \leq f(l,N)\)が成り立つことがわかります。

よって、\(f(l,r)\)をSegment Treeで求められるようにしておけば、各\(l\)について\(f(l,r)\geq x\)を満たす最小の\(r\)を二分探索により求めることができます。

したがって、判定問題を\(\Omicron(N\log N)\)で解くことができるため、\(A_i\)の最大値を\(M\)として、元の問題を\(\Omicron(N\log N\log M)\)で解くことができました。

また、Sliding Window Aggregation(SWAG)を用いれば、尺取り法により\(\Omicron(N\log M)\)で元の問題を解くこともできます。

実装例(SWAG)