First register for the contest here.
Idea: injxshn
Editorial: tch1cherin
Firstly, for each position the maximum bitwise OR we can get is the bitwise OR of the whole array. Let's denote it as total.
Then we compute an array $$$nxt$$$, where $$$nxt[i]$$$ is the smallest $$$j$$$ so that $$$OR(a[i], a[i + 1], ..., a[j - 1]) = total.$$$ Notice that $$$nxt[i] \le nxt[i + 1]$$$ so we can use two pointers to calculate this array. We also need some data structure that can find bitwise OR on the needed segments efficiently. It should be able to remove the first element from the segment and add a new element in the end. Basically, such data structure is a queue on two stacks. Basically, such data structure is a queue on two stacks (We do the same as in the article on cp-algorithms, but we keep the OR instead of the minimum).
So how to find the answer for each position? Let's denote the first element of an optimal segment for the current index $$$i$$$ as $$$j$$$. There are two cases:
$$$nxt[j] \le i$$$ This case is easy. In this case the answer is the minimum value of $$$i - j$$$ over all $$$j$$$ such that $$$nxt[j] \le i$$$, so we need to maximize $$$j$$$. When we are at the $$$j$$$-th index, we just "push" $$$j$$$ on the suffix $$$nxt[j]$$$..$$$n$$$.
$$$nxt[j] > i.$$$ In this case the answer is the minimum value of $$$nxt[j] - j$$$ over all $$$j$$$ such that $$$nxt[j] > i$$$. Let's keep optimal $$$j$$$-s in some data structure. Notice that if there are two positions $$$x$$$, $$$y$$$ such that $$$x < y$$$ and $$$nxt[x] - x \le nxt[y] - y$$$, we don't need to keep $$$x$$$ because it's never optimal. So in this data structure if $$$x < y$$$ then $$$nxt[x] - x < nxt[y] - y$$$. Let's store pairs $$${nxt[j] - j, nxt[j]}$$$ in a deque. When we add a new $$$j$$$, we delete useless elements from the end of the deque. Also we don't need keep $$$nxt[j]$$$ if it is less than $$$i$$$. So delete such $$$nxt[j]$$$(s) from the start of the deque. The answer for this case is $$$nxt[j] - j$$$ of the first element in the deque.
So we found the answer for each position and now we can answer each query in $$$O(1)$$$ making the overall time complexity of the code to be $$$O(n+q)$$$.
#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, q;
cin >> n >> q;
vector<int> a(n);
int total = 0;
for (int &value : a) {
cin >> value;
total |= value;
}
vector<array<int, 2>> st1 = {{0, 0}}, st2;
deque<array<int, 2>> hull;
vector<int> ans(n), nxt(n), push(n, -n);
for (int i = 0, j = 0; i < n; i++) {
if (i > 0) {
push[i] = max(push[i - 1], push[i]);
}
j = max(j, i);
while (j < n && (st1.back()[1] | (st2.empty() ? 0 : st2.back()[1])) < total) {
st1.push_back({a[j], st1.back()[1] | a[j]});
j++;
}
if (j < n) {
push[j] = max(push[j], i);
}
nxt[i] = j;
if ((st1.back()[1] | (st2.empty() ? 0 : st2.back()[1])) == total) {
while (!hull.empty() && hull.back()[1] > j - i) {
hull.pop_back();
}
hull.push_back({j, j - i});
}
while (!hull.empty() && hull.front()[0] <= i) {
hull.pop_front();
}
ans[i] = min(i - push[i] + 1, hull.empty() ? n : hull.front()[1]);
if (i == j) {
continue;
}
if (st2.empty()) {
while (st1.size() > 1) {
st2.push_back({st1.back()[0], (st2.empty() ? 0 : st2.back()[1]) | st1.back()[0]});
st1.pop_back();
}
}
st2.pop_back();
}
while (q--) {
int k;
cin >> k;
cout << ans[k] << "\n";
}
}