Description
我们定义一个数对 (x,y) 是好的，当且仅当 x≤y，且 x xor y的二进制表示下有奇数个 1
现在给定 nn 个区间 [li,ri]，你需要对于每个 i∈[1,n]，输出有几对好的数 (x,y)满足 x 和 y 都在 [l1,r1]∪[l2,r2]...∪[li,ri]，即两个数都在前 i 个区间的并里
Input
第一行一个正整数 n
接下来 n 行每行两个整数 [li,ri]，表示第 i个区间，保证 li≤ri
Output
输出 n 行，第 i行一个整数表示有几对好的数 (x,y) 满足 x,y 都在前 i 个区间的并里
Sample Input
3
1 7
3 10
9 20
Sample Output
12
25
100
Hint
对于 30%30% 的数据，有 1≤n≤1001≤n≤100，1≤li≤ri≤1001≤li≤ri≤100
对于 50%50% 的数据，有 1≤n≤10001≤n≤1000，1≤li≤ri≤232−11≤li≤ri≤232−1
对于 100%100% 的数据，有 1≤n≤1051≤n≤105, 1≤li≤ri≤232−11≤li≤ri≤232−1
时间限制：2s
空间限制：512MB
Solution
先补充几个小知识点（快速求出一个数的二进制中有多少个1）:
x=x&(x-1)（递归求法，适用于单个数） 表达式的意思就是:把x的二进制表示 从低位开始，将遇到的第一个为1的 二进制位 置0。
int calc=0;while(x) x=x&(x-1),calc++;calc即为所求值
求0到x中有多少二进制含1个数为奇数的：
long long calc(long long x){ long long tmp=x,tot=0; while(tmp) { if(tmp&1)tot++; tmp>>=1; } return (x>>1)+((x&1) || (tot&1));} 证明：00 01 10 11 100 101 110 111....继续下去可以发现规律是偶奇奇偶奇偶偶奇.... 所以x>>1之前一半的，如果x为奇数（会少算一个）或其本身有奇数个1得加上 p.s.当线段树叶子节点有n个时，应开总共2^(log2n+1)个点，即2*n个点
正经题解开始：
首先，对于每个数对（x,y）, 若要x xor y的二进制表示下有奇数个 1，则必定一者含奇数个1，一者含偶数个。
证明：若两个都为奇数，1.则奇减奇等于偶（重叠个数为奇个）2.奇减偶先为奇（重叠个数为偶数个），奇加奇等于偶
若两个都为偶数，则可同上证明
一奇一偶，1.奇减奇等于偶，偶减奇等于奇，奇加偶等于奇2.奇减偶等于奇，偶减偶等于偶，偶加奇等于奇
所以我们采取线段树来维护区间含奇数个1和含偶数个1的个数，对于区间l,r，则用上述中所介绍的calc函数，来calc(r)-calc(l-1)得到奇数个1个数以及r-l+1-（calc(r)-calc(l-1)）得到偶数个1个数
每次输入一个区间加进去统计一个区间，然后输出总的相乘即可。p.s.线段树很好的解决了区间相交的问题，在以及统计过的区间标记vis[now]=1;
上代码：
1 #include2 #define maxn 100005 3 using namespace std; 4 typedef long long ll; 5 ll num[maxn<<4][2]; 6 int lc[maxn<<4],rc[maxn<<4],rt=0,np=0; 7 int n; 8 bool vis[maxn<<4]; 9 void upload(int now){10 num[now][0]=num[lc[now]][0]+num[rc[now]][0];11 num[now][1]=num[lc[now]][1]+num[rc[now]][1];12 }13 ll calc(ll x)14 {15 ll t=x,tot=0;16 while(t)17 {18 if(t&1)tot++;19 t>>=1;20 }21 return (x>>1)+((x&1) || (tot&1));22 }23 void update(int &now,ll l,ll r,ll x,ll y){24 if(!now) now=++np;25 if(vis[now]) return;26 if(l>=x&&r<=y){27 num[now][1]=calc(r)-calc(l-1);28 num[now][0]=r-l+1-num[now][1];29 vis[now]=1;30 return;31 }32 ll m=(l+r)>>1;33 if(y<=m)update(lc[now],l,m,x,y);34 else if(x>m)update(rc[now],m+1,r,x,y);35 else{36 update(lc[now],l,m,x,y);37 update(rc[now],m+1,r,x,y);38 }39 40 upload(now);41 }42 void init(){43 scanf("%d",&n);44 ll L,R,mx=1ll<<32;45 for(int i=1;i<=n;i++){46 scanf("%lld%lld",&L,&R);47 update(rt,1,mx,L,R);48 printf("%lld\n",num[1][0]*num[1][1]);49 }50 }51 int main(){52 init(); 53 54 return 0;55 }