思路
关键观察：将区间右端点从 i−1 扩展到 i 时，任何以 i 结尾的子区间的按位或，要么等于 ai，要么是某个以前缀结尾的按位或再与 ai 做一次 ∣。并且按位或只会“开新位”不会关掉已有位，因此对于固定右端点 i，不同的“以 i 结尾的子区间按位或结果”的种类数是有限的，至多与二进制位数相关。由于 ai≤109，二进制位数 B≤31，所以每个位置最多保留 O(B) 个不同的结果。
做法（在线去重）：
-
维护两个集合：
- Sprev：所有“以前一个位置结尾”的按位或结果集合；
P3434.第3题-小红的区间或
题目内容
小红有一个长度为 n 的数组 a ，记子区间 [l,r] 的权值为 al∣al+1∣...∣ar ，即区间内所有数的按位或运算的结果。一共有 n×(n+1)/2 个子区间，小红想知道对应的 n×(n+1)/2 个权值中，有多少个不同的取值。
输入描述
第一行一个整数 n ，表示数组长度。
第二行 n 个整数 a1,a2,...,an ，表示数组 a 的元素。
1≤n≤105
1≤ai≤109
输出描述
输出一个整数，表示不同的取值个数。
样例1
输入
3
1 2 4
输出
6
说明
[1,1] 的权值为 1
[1,2] 的权值为 3
[1,3] 的权值为 7
[2,2] 的权值为 2
[2,3] 的权值为 6
[3,3] 的权值为 4
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
