题目描述：
给你一个长度为 n 下标从 0 开始的数组 nums ，数组中所有数字均为非负整数。对于 0 到 n - 1 之间的每一个下标 i ，你需要找出 nums 中一个 最小 非空子数组，它的起始位置为 i （包含这个位置），同时有 最大 的 按位或**运算值** 。
- 换言之，令
Bij 表示子数组 nums[i...j] 的按位或运算的结果，你需要找到一个起始位置为 i 的最小子数组，这个子数组的按位或运算的结果等于 max(Bik) ，其中 i <= k <= n - 1 。
一个数组的按位或运算值是这个数组里所有数字按位或运算的结果。
请你返回一个大小为 n 的整数数组 answer，其中 answer[i]是开始位置为 i ，按位或运算结果最大，且 最短 子数组的长度。
子数组 是数组里一段连续非空元素组成的序列。
数据范围：
$1\le n \le 10^5, 0\le nums[i] \le 10^9$
题解：
使用 logtrick 模板
1
2
3
4
5
6
| for(int i = 0; i < n; ++i) {
for(int j = i - 1; j >= 0; --j) {
if(nums[j] | nums[i] == nums[j]) break;
}
}
|
需要用一个 maxx[i] 数组表示从 $i$ 到末尾子数组或值最大的结果。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
vector<int> smallestSubarrays(vector<int> &nums)
{
int n = nums.size();
vector<int> maxx(n);
vector<int> ans(n);
for (int i = 0; i < n; ++i)
{
maxx[i] = nums[i];
ans[i] = 1;
for (int j = i - 1; j >= 0; --j)
{
if ((nums[j] | nums[i]) == nums[j])
{
break;
}
nums[j] |= nums[i];
if (nums[j] > maxx[j])
{
maxx[j] = nums[j];
ans[j] = i - j + 1;
}
else if (nums[j] == maxx[i])
{
if (i - j + 1 < ans[j])
{
ans[j] = i - j + 1;
}
}
}
}
return ans;
}
};
|