より制約が強化された問題が出題されており、その問題の解説に\(\Omicron(\log N \log K)\)で解く方法が示されています。詳細はリンク先の解説を参照してください。