Subarrays BeautySubarrays Beauty (位运算)解题报告

http://codeforces.com/gym/101532/problem/A

题意

给定长度为n的数，要求求所有子区间内的数进行与运算（&）的和

解题报告

对于一个数来说变成二进制的后可以变成二进制数位之和，例如：
7=12^0+1*21+12^2; 11=12^0+1*21+02^3+1*24;
因此根据与运算特性一旦出现了0&前面的数一定会变成0，要重新开始算,再讨论所有区间就完了。拿样例1来说：
a[1]=7，a[2]=9，a[3]=11可以看成
a[1]=0111
a[2]=1001
a[3]=1011
对于二进制第j位a[i][j-1],假设在区间(l,r)都是连续的1,因此这个区间内1的个数是(r-l+1)*(r-l+2)/2。
我们看看样例的第一个二进制位是111,区间是(1,3)，它的子区间分别是(1,1)(1,2)(1,3)(2,2)(2,3)(3,3)也可以写成
(1,1)(2,1)(2,2)(3,1)(3,2)(3,3)（这里只是数的方向不同)，因此公式就出来了。
下面代码(里面有个通过对数直接取最大二进制位数的优化，不知道为什么我用C++一定会超时，换了c直接a了)

代码

#include<iostream>
#include<stdio.h>
#include<bitset>
#include<cmath>
using namespace std;
const int maxn=1e5+5;
bitset<31>a[maxn];
int main()
{
	int T;
	while(scanf("%d",&T)!=EOF)
	{
		while(T--)
		{
			int n,temp;
			int set=0;
			scanf("%d",&n);
			for(int i=0;i<n;i++)
			{
				scanf("%d",&temp);
				set=max(set,(int)log2(temp)+1);
				a[i]=bitset<31>(temp);
			}
			long long ans=0;
			a[n]=bitset<31>(0);
			for(int i=0;i<set;i++)
			{
				long long rco=0;
				int  flag=0;
//				cout<<"+++++++=flag="<<flag<<endl;
				for(int j=0;j<n+1;j++)
				{
					if(flag==0)
					{
						if(a[j][i]==1)
						{
							rco++;
							flag=1;
						}
					}
					else
					{
						if(a[j][i]==1)
						{
							rco++;
						}
						else
						{
							flag=0;
							ans+=(1<<i)*(long long)rco*(rco+1)/2;
							rco=0;
						}
					}
//					cout<<"j="<<j<<" "<<"flag="<<flag<<" "<<rco<<" "<<ans<<endl;
				}
//				cout<<"--------------------"<<endl;
			}
			cout<<ans<<endl;
		}
	}
 } 

Q.E.D.