#1647. 无聊的数对

无聊的数对

题目描述

如果一个数对 (x,y) (x,y) 是无聊的,当且仅当 xy x\leq y,且 x xor y x~ \mathrm{xor}~y 的二进制表示下有奇数个 1 1

如果让你求 [1,n][1,n] 内的所有无聊的数对,那实在是太简单辣!

所以为了使得题目毒瘤一点,给出 nn 个区间 [li,ri][l_i,r_i],你需要数出有几对无聊的数 (x,y)(x,y) 满足 xxyy 都在 [l1,r1][l2,r2]...[li,ri] [l_1,r_1] \cup [l_2,r_2]... \cup [l_i,r_i],即两个数都在前 i i 个区间的并里。

输入格式

第一行一个正整数 n n

接下来 n n 行每行两个整数 [li,ri] [l_i,r_i],表示第 i i 个区间,保证 liri l_i\leq r_i

输出格式

输出n n 行,第i i 行一个整数表示有几对无聊的数 (x,y) (x,y) 满足 x,y x,y 都在前 i i 个区间的并里。

样例

5
1 7
3 10
5 7
4 111
222 12838
12
25
25
3080
40500496

数据范围与提示

对于 30% 30\% 的数据,有 1n100 1\leq n\leq 100, 1liri1001\leq l_i\leq r_i \leq 100

对于 50% 50\% 的数据,有 1n10001\leq n\leq 10001liri23211\leq l_i \leq r_i \leq 2^{32}-1

对于 100% 100\% 的数据,有 1n1051\leq n \leq 10^5, 1liri23211\leq l_i \leq r_i \leq 2^{32}-1