Description Abathur采集了一系列Primal Zerg 的基因样本，这些基因构成了一个完整的进化链。为了方便，我们用A0,A1…An-1 这n 个正整数描述它们。
一个基因Ax 可以进化为序列中在它之后的基因Ay。这个进化的复杂度，等于Ax | Ax+1…| Ay的值，其中| 是二进制或运算。
Abathur 认为复杂度小于M 的进化的被认为是温和的。它希望计算出温和的进化的对数。 Input 第一行包含两个整数n,m。
接下来一行包含A0,A1…An-1 这n 个正整数，描述这n 个基因。 Output 第一行包含一个整数，表示温和的进化的对数。 Sample Input 4 6
1 3 5 1 Sample Output 2 Data Constraint 对于30% 的数据，1 <= n <=1000。
对于100% 的数据，1 <= n<= 100000，0 <= m <= 2^30，1<= Ai<= 2^30。
前注： 比赛的时候被二分和树状数组迷住了心智： 欸？满足性质可以二分耶！ 欸？树状数组怎么维护区间或值？？？ 然后乱搞骗了30分。比赛出来一看正解：二分+线段树维护 ……我………………woc…………
思路： 首先要说为什么可以二分？ 因为or不会让数变小（这个不清楚的自己写写画画），就是说一路or过去，一定是非递减的 满足这个，就可以二分了 先用线段树维护区间的or值 然后用一个循环枚举开头，剩下的部分二分寻找一个离开头最远的合法值 （这里的距离用线段树维护） 每次累加长度输出 时间复杂度O（nlog2（n））
注：注意累加的答案用int64
代码：
const maxn=100001; var ans:int64; tree:array[0..4*maxn]of longint; a:array[0..maxn]of longint; n,m,i,j,x,tot,mid,l,r:longint; procedure maketree(x,l,r:longint); var mid:longint; begin if l=r then begin tree[x]:=a[l]; exit; end; mid:=(l+r)shr 1; maketree(2*x,l,mid); maketree(2*x+1,mid+1,r); tree[x]:=(tree[2*x] or tree[2*x+1]); end; function solve(x,y,t,l,r:longint):longint; var mid:longint; begin if (x=l)and(y=r) then exit(tree[t]); mid:=(l+r)shr 1; if y<=mid then exit(solve(x,y,2*t,l,mid)) else if x>mid then exit(solve(x,y,2*t+1,mid+1,r)) else exit((solve(x,mid,2*t,l,mid)or solve(mid+1,y,2*t+1,mid+1,r))); end; begin assign(input,'evolve.in');reset(input); assign(output,'evolve.out');rewrite(output); read(n,m); for i:=1 to n do begin read(x); if x<m then begin inc(tot); a[tot]:=x; end; end; n:=tot; maketree(1,1,n); for i:=1 to n do begin l:=i; r:=n; while l<=r do begin mid:=(l+r)shr 1; if (solve(i,mid,1,1,n))<m then l:=mid+1 else r:=mid-1; end; ans:=ans+r-i; end; writeln(ans); end.