Toosay
原题：（权限限制没有链接）
题目描述
在一个遥远的村庄，生活着淳朴自然的村民们，比如zd、crt、liaoy、pb等等淳朴的村民。
每天早上起来，他们就十分关心别人昨夜与周公做了什么，于是他们开始互相问话。可是作为一名淳朴的村民，每天要干的事情很多，如果每天起床就要记下自己问过谁了，还有谁没问，实在有些费劲哈。于是机智的pb想出了一个有趣的方法：
起床后大家排成一列，每个人都要把这队列中所有的人(包括自己)都问完，这样就不用再用脑子去记了。
可是同样机智的zd发现一个问题：刚刚liaoy跑过来问了我，等下我还要跑过去再问他一遍，这不是浪费体力啊。为什么不一起问呢？
这时机智的crt想到了一个方法：每个人都只问排在他后面的人(包括自己)，这样就避免了多跑路。
于是这个问题得到了解决。那么真正的问题来了：
每个村民身上都带有一个数字(可以相同)，然后每个村民去问话的路上(沿着队伍往后走)都会想把看到的数字(一开始会先看看自己的数字)记下来，可是村民太多了，想记下来实在费劲。于是机智的liaoy说：可以把每次看到的数和自己已经记下的数xor一下，更新自己记下的数。此时从这个村民到后面一个村民的所有数字xor起来便是这次问话的xor数字价值了。
这是一个好办法，为了提高准确性，于是哈某援例，说不如再记下and和、or和。为了判断某一个人是否和所有人(包括自己)都互相问过了。让你输出这些所有问话的xor数字价值之和，and数字价值之和，or数字价值之和。
特殊的，一个村民问自己时，并不需要xor、and、or俩次。因为他只会看一眼。(ps:为什么要问自己啊？因为他怕不记得自己的梦了啊。)
输入输出格式
输入格式：
第一行一个正整数n。
第二行为n个正整数a，第i个数，即第i个村民身上的数。
输出格式：
第一行xor 和
第二行and和
第三行or和
输入输出样例
输入样例#1：
3 1 2 3
输出样例#1：
10 8 15
说明
比如村民1跑去问村民3，那么此次xor数字价值：1 xor 2 xor 3=0。
村民1问自己，此次xor数字价值 ：1。
ansXor=1+2+3+1xor2+2xor3+1xor2xor3=1+2+3+3+1+0=10
ansAnd=1+2+3+1and2+2and3+1and2and3=1+2+3+0+2+0=8
ansOr=1+2+3+1or2+2or3+1or2or3=1+2+3+3+3+3=15
数据范围：n<=10^6 a<2^20
个人解法：
题目是求一个序列的子序列的And、Or、Xor和。
最初没有什么想法，只想到一个O(n^2)的暴力。
枚举端点O(n^2)，剩下的就是O(1)计算答案了。
Xor支持区间减法，于是我们可以做一个前缀和。而And与Or仅仅支持区间加法，不支持区间减法，怎么办呢……
突然发现And与Or都是基于位上的0与1的。
想到某锟前几天讲的拆位。因为位运算的位之间相互不影响，于是我们分别对每一位考虑。如果我们知道这一个区间在这一位上有多少个1（也就知道了有多少个0），于是就知道了这一段区间在这一位上的And与Or的值。
而前缀和是支持区间减法的。于是就用数组记录每一位上的前缀和就好了。
这样就可以O(n^2)得到答案了。
代码如下：
const
shl1:array[0..22] of longint=(1,2,4,8,16,32,64,128,256,512,1024,2048,4096,
8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304);//储存2的i次方
//xor can used A[i] (by Xorsum[i])
//And can used [0..20] of 0/1 (by [0..20] Andsum)
//Or can used [0..20] od 0/1 (by [0..20] Orsum)
var
A,Xorsum:array[0..1000010] of longint;
Seat:array[0..1000010,0..22] of longint;//Seat记录前面有某一位上的前缀和
Temp:array[0..22] of longint;
Ans:array[1..3] of int64;//1 is xor,2 is And,3 is Or
n,i,j,len,block,Done,Andtmp,Ortmp:longint;
begin
read(n);
for i:=1 to n do//处理数字
begin
read(A[i]);
for j:=1 to 3 do
inc(Ans[j],A[i]);
Xorsum[i]:=A[i] xor Xorsum[i-1];
len:=0;
fillchar(Temp,sizeof(Temp),0);
while A[i]<>0 do
begin
if A[i] and 1=1 then Temp[len]:=1;
A[i]:=A[i] shr 1;
inc(len);
end;
for len:=0 to 22 do
Seat[i,len]:=Seat[i-1,len]+Temp[len];
end;
for len:=2 to n do//枚举端点
for i:=1 to n do
begin
j:=i+len-1;
if j>n then break;
inc(Ans[1],Xorsum[j] xor Xorsum[i-1]);
Andtmp:=0;
Ortmp:=0;
for block:=0 to 22 do
begin
Done:=Seat[j,block]-Seat[i-1,block];
if Done>0 then inc(Ortmp,shl1[block]);
if Done=j-i+1 then inc(Andtmp,shl1[block]);
end;
inc(Ans[2],Andtmp);
inc(Ans[3],Ortmp);
end;
writeln(Ans[1]);
writeln(Ans[2]);
writeln(Ans[3]);
end.
（tm这个暴力有鬼用啊）
嗯这个暴力虽然不能过全部数据，但是也在考场上启发了我。
（然而考场上想出很好的解法时，只有0.5hour的时间，啥也写不出了）
继续考虑拆位。接下来的讨论对于一个位上的0/1讨论。
思考位运算的法则。
对于And而言，只有一个区间全部是1的时候，这一位的And才会是1。如果我们知道了有多少个区间全部为1，那么也就知道了这一位对And的贡献了。
这是可以O(n)扫一遍出来的。
接下来考虑Or，只要一个区间有一个1，这一位的Or就会是1。如果我们知道了有多少个区间全部为0，那么也就知道了有多少个区间有一位是1，也知道这一位对Or的贡献了。
这个和And一样扫一边就可以了。
接下来考虑Xor。如果一个区间有奇数个1，这一位的Xor就会是1；如果一个区间有偶数个1，这一位的Xor就会是0。
于是我们考虑从后面开始扫描。假设F[i]表示以第i位为左端点的区间中，有奇数个1的区间个数。那么F[i]=n-i+1-F[j]，其中j为i往右边数第一个1的位置。
这样就可以O(n)扫出来了。
代码如下：
const
shl1:array[0..22] of longint=(1,2,4,8,16,32,64,128,256,512,1024,2048,4096,
8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304);
All=20;
//xor can used A[i] (by Xorsum[i])
//And can used [0..20] of 0/1 (by [0..20] Andsum)
//Or can used [0..20] od 0/1 (by [0..20] Orsum)
var
A:array[1..1000040,0..All] of Byte;
F:array[1..1000040,0..All] of longint;
n,i,w,l,last,j:longint;
Ans,sum,len:int64;
begin
read(n);//数据处理
for i:=1 to n do
begin
read(w);
l:=0;
while w<>0 do
begin
A[i,l]:=w and 1;
w:=w shr 1;
inc(l);
end;
end;
//Xor运算
Ans:=0;
for i:=0 to All do
begin
last:=n+1;
sum:=0;
for j:=n downto 1 do
begin
if A[j,i]=1 then
begin
F[j,i]:=n-j+1-F[last,i];
last:=j;
end
else F[j,i]:=F[last,i];
inc(sum,F[j,i]);
end;
inc(Ans,sum*shl1[i]);
end;
writeln(Ans);//输出
//And运算
Ans:=0;
for i:=0 to All do
begin
last:=-1;
sum:=0;
A[n+1,i]:=0;
for j:=1 to n+1 do
if A[j,i]=1 then
begin
if last=-1 then last:=j;
end
else
if last<>-1 then
begin
len:=j-last;
inc(sum,len*(len+1) shr 1);
last:=-1;
end;
inc(Ans,sum*shl1[i]);
end;
writeln(Ans);//输出
//Or运算
Ans:=0;
for i:=0 to All do
begin
last:=-1;
sum:=0;
A[n+1,i]:=1;
for j:=1 to n+1 do
if A[j,i]=0 then
begin
if last=-1 then last:=j;
end
else
if last<>-1 then
begin
len:=j-last;
inc(sum,len*(len+1) shr 1);
last:=-1;
end;
sum:=int64(n)*int64(n+1) shr 1-sum;
inc(Ans,sum*shl1[i]);
end;
writeln(Ans);//输出
end.
位运算劲啊。