これのオンライン版：https://competitive.hamadu.net/entry/2016/10/01/001418
なので、永続セグ木実装すれば解けるけど、実装が理解できない...（アプローチは分かる）