2020牛客多校第五场 H. Interval 题意: 给定长度为 的数组 ,定义 ,。有 次询问,每次询问给定 和 ,取 ,求 ,其中 为上一次询问的答案,初始值为 。 链接: https://ac.nowcoder.com/acm/contest/5670/H 解题思路: 考虑单次询问的暴力做法,对询问 ,枚举子区间右端点,扩展左端点,将所有位与出来的值去重后的个数就是答案,这样复杂度起码是单次 的。 进一步分析可以得到,对于 ,向左扩展的出的不同数是严格递减的(更进一步,二进制位的 的个数的递减的),一个 只会扩展出 个不同的数,此时优化了暴力做法,但预处理之后每次询问需...