显然,对于正整数 p,qp,qp,q,设 p,qp,qp,q 在二进制表示下的位数分别为 x,yx,yx,y,若 p≤qp\le qp≤q,则:
要注意,对于任意非负整数 mmm,都满足 0≤0⊕m≤m0 \le 0 \oplus m \le m0≤0⊕m≤m,所以需要特判 000。
在特判 000 后,我们可以把剩下的元素从小到大排序,开一个桶,把枚举过的数在二进制表示下的位数记录在桶里,动态地根据上面的讨论计算即可。
时间复杂度 O(nlogn+nlogV)\mathcal O(n \log n+n \log V)O(nlogn+nlogV),其中 VVV 为值域。
注册一个 MXOJ 通用账户,您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 MXOJ 通用账户