atcoder ARC092 D
今天生日捏，嘻嘻~
题意：给定A B数组长度为n 求所有 （1<=i，j <=n ） a[i]+b[j] 的异或和。 n <=200000 ai bi <=228
这题比赛没写出来，而且完全没思路，结束后看了zz大佬的博客大致有了解题方向，然后再参考了cyc的...于是大致会写了。
由于xor 实际上是每一位的xor ，所以考虑一位一位的算出答案。（即算出答案在二进制下的每一位的数字 0 或 1）
ps：以下的每一个数都为二进制，位数从右往左数。
可以证明，已知 某一位上有 x 个 1 y 个0 的话， 这一位上xor后为 x mod 2。
这样就将问题转换为： 求所有 a[i]+b[j] 在二进制下，每一位分别的 1 的个数 之和。
举个栗子！
如样例
001 010
011 100
a[i]+b[j]分别为：
100
101
101
110
第1位有0 1 1 0 共2个 1 mod 2后为 0 (从左往右的第3位)
第2位有0 0 0 1 共1个 1 mod 2后为 1 (从左往右的第2位)
第3位有1 1 1 1 共4个 1 mod 2后为 0 (从左往右的第1位)
于是答案就是 (010)2=(2)10
然后就可以开始一位位的考虑了
当我们计算答案的第 k 位时，发现 a[i] b[j] 的k+1位之后的 （如当k=2 ，a[i]=100，那么k+1为之后的即 1）
对第k位的答案是没有作用的，因为当a[i]+b[j]后，k+1位之后的数对k没有任何影响。
所以就可以将k+1之后的都给扔掉。
于是我萌设
c[i]=a[i] and ((1 << k)-1)
d[i]=b[i] and ((1 << k)-1)
and ((1 << k)-1) 就相当于可以把k位都拿出来了
如 一个数10101110 k=4 那么
10101110 and
00001111
=00001110
至于为什么可以就自己思考一下。
由于0的个数是没有用的，所以考虑1就好了
发现0<=c[i]，d[j]< 2k
对于第k位可以有一个 1
只有满足
①2k-1<=c[i]+d[j]<2k 这个就相当于
c[i]+d[j]没有向下一位进 1 而且第 k 位会是 1 因为 2k-1 相当于在第k位有一个1 其他都为0 而2k 相当于第k+1位有一个1其他都为0
这样的一个范围里就包含了所有第k位是1的所以数 ，而c[i]+d[j] 在这个范围里 所以说明对第 k 位有一个1 的贡献。
或
②2k+2k-1<=c[i]+d[j]<2k+1
类比第一个，这个就是对下一位进1 后的且第k为是1。
一样可以得到这样的一个范围能满足 第k+1位是1 且 第k位是1。
那到底有多少个c[i]+d[j] 是在以上的两个范围的其中一个
只要求出有多少个这样的数对 （i，j） 满足 c[i]+d[j] 是以上两个范围里的其中一个，问题就解决了（求出了有多少个1了）
考虑固定 j 移动 i
把c数组从小到大排序。
只要找到最左的 i （L）和最右的 i（R） 这样由于单调性 L~R 中的 i 都是满足条件的，所以 R-L+1即是1的个数。
所以分两类 分别计算出两类的个数加起来即可
而对于L R 用二分就好了。
这题是我接触的比较新的题，写详细些，自己因为二分一个小地方敲错了一直tle，以后要注意。
最后的话，生日快乐！
int64; 4 m1:int64; 5 ans,x,y:int64; 6 procedure qs(l,r:longint); 7 var i,j,m,t:longint; 8 begin 9 i:=l; 10 j:=r; 11 m:=c[(l+r)>>1]; 12 repeat 13 while c[i]<m do inc(i); 14 while c[j]>m do dec(j); 15 if i<=j then 16 begin 17 t:=c[i];c[i]:=c[j];c[j]:=t; 18 inc(i); 19 dec(j); 20 end; 21 until i>j; 22 if l<j then qs(l,j); 23 if i<r then qs(i,r); 24 end; 25 function find(x:int64):longint; //找到第一个 x>=c[i] 的 i。 26 var l,r,m:longint; 27 begin 28 l:=1; 29 r:=n; 30 while l<=r do 31 begin 32 m:=(l+r)>>1; 33 if c[m]<x then l:=m+1 else r:=m-1; 34 end; 35 exit(l); 36 end; 37 begin 38 read(n); 39 for i:=1 to n do 40 read(a[i]); 41 for i:=1 to n do 42 read(b[i]); 43 c[0]:=-1; 44 c[n+1]:=1 << 45; 45 for k:=1 to 29 do 46 begin 47 x:=1 << k; //即x=2k 48 y:=1 << (k-1); //即 y=2k-1 49 for i:=1 to n do 50 begin 51 c[i]:=a[i] and (x-1); 52 d[i]:=b[i] and (x-1); 53 end; 54 qs(1,n); //排序C数组 55 m1:=0; //m1表示答案的第k位有多少个1 56 for j:=1 to n do 57 begin 58 m1:=m1+find(x-d[j])-find(y-d[j]); 59 //满足第 k位是 1 的第一种情况 2k-1<=c[i]+d[j]<2k
60 //两边都减 d[j] 得 2k-1-d[j]<=c[i]<2k-d[j]
//也就是说对于 所有满足这个范围的c[i] 都能使第 k 位是 1 find(x-d[j])
//就是最右的 i+1
//(为什么有个+1？因为find找的是 >=的而范围只有 >,所以find会找到满足这个范围的最右的 i 的下一个)
//由于答案为 最右的i - 最左的i +1 （类似 r-l+1） 而find(x-d[j]) 多加了个 1 所以计算时不再 +1
//而是 find(x-d[j])-find(y-d[j]); 61 m1:=m1+n+1-find(x+y-d[j]);
//这个就是第二种情况 类似于第一种就好啦 62 end; 63 if m1 and 1 =1 then ans:=ans+y; 64 end; 65 writeln(ans); 66 end.