暴力即可。
对每一位滚一个前缀和就好,查询就对每一位查能否为 111。
二进制问题就按位做,考虑 l∼rl\sim rl∼r 中是否存在一个数满足二进制第 iii 位为 111。
考虑贪心的构造尽量一个大的满足 ≤r\le r≤r 的数,那么肯定是找到 rrr 中第 j(j>i)j(j>i)j(j>i) 位为 111 的位置,把这一位变成 000,更高的位不动,第 jjj 位后面的全部变成 111,那么这是一个合法的 ≤r\le r≤r 且最大的数,检查其是否 ≥l\ge l≥l 即可。
时间复杂度 O(Tlog2r)\mathcal{O}(T\log_2 r)O(Tlog2r)。
使用您的 Hydro 通用账户