题意：求n个整数任意取一个区间，一起进行xor，and，或or的操作，求xor的期望值，and的期望值，or的期望值。
思路：区间取的左端点为l，右端点为r，当r==l时，选的概率为1/n/n，而r！=l时，选的概率为2/n/n。
然后因为进行二进制操作，所以枚举整数的每个二进制位。三个操作分三种情况：
1and：考虑先枚举一个右端点r,考虑and的性质,所以考虑找到前面第一个0出现的位置last[0],如果这一位也为1,那么左端点就可以取[last[0]+1,r−1]。
2or：依然考虑枚举右端点r,找到前一个1出现的位置last[1],如果这一位为1,那么左端点可以取[1,r−1],如果这一位不为0,那么左端点可以取[1,last[1]]。
3xor：算法竞赛进阶指南上写得很详细。
首先依然是枚举右端点r，因为xor的性质,所以考虑找到所有为1的点,然后根据这些点进行黑白染色,就会是左端点可以取所有白段，最后再递推一下。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<vector>
#include<string>
#include<set>
#define ll long long
using namespace std;
const int N=1e6+10;
int n;
int a[N],b[N];
double ansa,anso,ansx;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int k=0;k<31;k++)
{
int last[2]={0,0},c1=0,c2=0;
for(int i=1;i<=n;i++)
{
b[i]=((a[i]>>k)&1);
if(b[i])
{
ansa+=(1<<k)*1.0/n/n;
anso+=(1<<k)*1.0/n/n;
ansx+=(1<<k)*1.0/n/n;
}
}
for(int i=1;i<=n;i++)
{
if(!b[i])
{
anso+=(1<<k)*2.0/n/n*last[1];
}
else
{
ansa+=(1<<k)*2.0/n/n*(i-1-last[0]);
anso+=(1<<k)*2.0/n/n*(i-1);
}
ansx+=(1<<k)*2.0/n/n*(b[i]?c1:c2);
c1++;
if(b[i])
swap(c1,c2);
last[b[i]]=i;
}
}
printf("%.3lf %.3lf %.3lf\n",ansx,ansa,anso);
}