しゃくとり法は
のけんちょんさんの記事のとおり、ある条件下での区間の数え上げを、区間の両端を決めるためのO(n^2)から、O(n)に落とせるテクニックである。
満たすべき条件
条件を満たす区間の端は単調にしか変化しない！だけ
簡単に言うと、[l, r)が条件を満たさないとき、
[l, r + x) (xは妥当な自然数)は条件を満たさない！
ということである。
ということである。
これをもっと突き詰めて言うと、
条件を含む区間の連続部分列、([l, r)が条件を満たすのなら、l <= x and y < rを満たすすべての[x, y))でも条件を満たす
そして、これを満たすものには操作自体に単調性を持つので、二分探索の計算時間的な上位互換になることが多い。
もちろんすべての二分探査を代替できるわけではない。数列で決め打ちしての二分探索の代替ができるだけである。
例 ARC098 D(500)
この問題では、上の性質がよくあてはまる。
条件自体は、与えられた区間の中で、すべてのbitで1がたかだか1つしか現れない、ということである。
単調性は一見ないように見えるが、よく見ると、条件を満たす区間の中のすべての部分区間も条件を満たさないといけない。
条件自体は、与えられた区間の中で、すべてのbitで1がたかだか1つしか現れない、ということである。
単調性は一見ないように見えるが、よく見ると、条件を満たす区間の中のすべての部分区間も条件を満たさないといけない。
区間内で一度1が2つ以上現れる桁があるのなら、それを連続部分列として含むほかのすべての区間もだめになる。
よって、今の区間が条件を満たすのなら、必ずすべての連続部分列の区間は条件を満たす。
よって、今の区間が条件を満たすのなら、必ずすべての連続部分列の区間は条件を満たす。
これはしゃくとりそのものであるので、しゃくとりをそのまま実装すればよい。
ソースコード：
