思路

关键观察：将区间右端点从 $i-1$ 扩展到 $i$ 时，任何以 $i$ 结尾的子区间的按位或，要么等于 $a_i$，要么是某个以前缀结尾的按位或再与 $a_i$ 做一次 $|$。并且按位或只会“开新位”不会关掉已有位，因此对于固定右端点 $i$，不同的“以 $i$ 结尾的子区间按位或结果”的种类数是有限的，至多与二进制位数相关。由于 $a_i\le 10^9$，二进制位数 $B\le 31$，所以每个位置最多保留 $O(B)$ 个不同的结果。

做法（在线去重）：

• 维护两个集合：

  • $S_{\text{prev}}$：所有“以前一个位置结尾”的按位或结果集合；
  • $S_{\text{cur}}$：所有“以当前位置 $i$ 结尾”的按位或结果集合。

题目内容

小红有一个长度为 $n$ 的数组 $a$ ，记子区间 $[l,r]$ 的权值为 $a_l|a_{l+1}|...|a_r$ ，即区间内所有数的按位或运算的结果。一共有 $n×(n+1)/2$ 个子区间，小红想知道对应的 $n×(n+1)/2$ 个权值中，有多少个不同的取值。

输入描述