2013 ACM/ICPC Asia Regional Chengdu Online–1010

hdoj4737 A Bit Fun
题意:给出n,m,然后给你n个正整数(n<=10^5),设f(i,j)=ai|ai+1|ai+2|……|aj,(i<=j),问有多少不同的f(i,j)<m.
总体思路:假如有一段连续的数[ai……aj aj+1],由于位或运算会使得结果越来越大,所以f(i,j)<f(i,j+1),那么可以很快得到二分的算法:一次枚举第i个数,二分[i,n]这一段数,找到最大的t,满足f(i,t)<m.
但是问题是n是10^5,每次暴力计算f(i,j)都是O(n)的(这样做就没有二分),这样复杂度是O(n^2)的,怎么降低复杂度呢(貌似这题数据比较水,比赛的时候很多大一队员是用暴力水过的,,==!)。
关键在于要常数时间计算ai|ai+1|ai+2|……|aj。可以这样做,a[i][k]表示前i个数对应第k位(把数分解成二进制)上“1”的个数之和,显然如果a[i-1][k]<a[j][k],那么说明[ai,aj]这段连续的数中至少存在一个数它的第k位是“1”,那么这段数位或起来,结果的二进制第k位一定是“1”,反之亦然。这样枚举结果的每一位分别是1还是0即可,一个数最多30位,自然是常数。