jzoj. 3518. 【NOIP2013模拟11.6A组】进化序列(evolve)

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。

注意：本人的题解比较奇怪，理解不了的可以看其他的题解。

分析：
对于一个数x，把k=x or y (y为任意数)，我们可以知道 k>=x。那么我们有普通方法暴力O(n^2)求一个区间的or值。显然，当一个区间继续or下一个数，得到的一定是个递增的序列。在这个序列中找小于m的数，我想大家也知道用二分法。

对于每一个mid，我们都要求一次or和吗？今天有个大神说可以用一个队列解决，把右边的指针往右移直到or值大于等于m，再移左指针，继续移右指针，但是没有or的逆运算，但我觉得这种方法还是可以的，不过要点其他操作，请各位大神帮忙解决。

在二分无果后，我们考虑倍增。我们每次增加2^k个数的or值。如果打过rmq的大神应该知道，这可以O(nlogn)处理，对于每个起点也跑一次倍增，也是O(nlogn)，这题就解决了。

f[i,j]表示从第i个数开始，往后2^j个数的or和，显然有（有点像rmq的样子）：
f[i,j]=f[i,j-1] or f[i+2^(j-1),j-1]

我们处理出这个后，就可以倍增法过了。pas的trunc(ln(n)/ln(2))可能出现误差，导致WA。今天我后面每个点几乎就差1，错了。然后看了下ln(1024)/ln(2)=9.999，一个trunc就永远跳不到1024了，吸取教训。

代码：

const
 maxn=100001;
var
 f:array [1..maxn,0..20] of longint;
 a:array [1..maxn] of longint;
 n,m,i,j,k,t,x,sum,q:longint;
 ans:int64;
begin
 assign(input,'evolve.in');
 assign(output,'evolve.out');
 reset(input);
 rewrite(output);
 readln(n,m);
 for i:=1 to n do
  begin
   read(a[i]);
   f[i,0]:=a[i];
  end;
 for j:=1 to trunc(ln(n)/ln(2)) do
  for i:=1 to n-(1 shl j)+1 do
    f[i,j]:=f[i,j-1] or f[i+1 shl (j-1),j-1];

 for i:=1 to n do
  begin
   if a[i]>=m then continue;
   t:=i; x:=trunc(ln(n-i+1)/ln(2)+0.00001);
   sum:=0; q:=0;
   while x>=0 do
    begin
     if t+1 shl x<=n+1 then
      if sum or f[t,x]<m then
      begin
       sum:=sum or f[t,x];
       t:=t+1 shl x;
       q:=q+1 shl x;
      end;
     x:=x-1;
    end;
   ans:=ans+q-1;
  end;
 writeln(ans);
 close(input);
 close(output);
end.