从小号搬一下。
key observation：若一个区间合法，则最后覆盖整个区间的数一定是它的按位或和。
证明很简易：操作不会影响区间按位或和。
然后分类讨论得到如下结论：
-
区间内有 \(\ge 2\) 个等于区间按位或和的数时，有解。
-
区间内有 \(1\) 个等于区间按位或和的数，同时区间内有不与这个数位置有交的子区间，且其按位或和等于这个数时，有解。
-
其他情况无解。
考虑统计。一个经典结论，对于每个固定的左端点 \(x\)，会有 $ O(\log V)$ 种不同的区间按位或和取值。所以对于 \(x\)，会有 $ O(\log V)$ 个右端点的取值区间 \([l,r]\)。我们可以表示成三元组 \((x,l,r)\)。
把三元组差分到 \(l\) 和 \(r + 1\) 上，把询问挂在右端点上，离线下来扫描线。线段树和 set 维护两种情况：答案子区间右端点为 \(r\)、答案子区间右端点为当前询问右端点。
关于预处理三元组，按照结论模拟即可。
时间复杂度 \(O(n\log n\log V)\)，空间复杂度 \(O(n\log V)\)。需要一定的卡常技巧。
感觉放代码没什么用，但还是贴上
#include <bits/stdc++.h>
using namespace std;
#define rep(i, x, y) for (int i = (x); i <= (y); i++)
#define per(i, x, y) for (int i = (x); i >= (y); i--)
struct IO {
static const int inSZ = 1 << 17;
char inBuf[inSZ], *in1, *in2;
template<class T> inline __attribute((always_inline))
T read() {
if (in1 > inBuf + inSZ - 32) [[unlikely]] {
auto len = in2 - in1;
memcpy(inBuf, in1, len);
in1 = inBuf, in2 = inBuf + len;
in2 += fread(in2, 1, inSZ - len, stdin);
if (in2 != inBuf + inSZ) *in2 = 0;
}
T res = 0;
unsigned char c;
bool neg = 0;
while ((c = *in1++) < 48) neg = c == 45;
while (res = res * 10 + (c - 48), (c = *in1++) >= 48);
return neg ? -res : res;
}
static const int outSZ = 1 << 21;
char outBuf[outSZ], *out;
template<class T> inline __attribute((always_inline))
void write(T x) {
if (out > outBuf + outSZ - 32) [[unlikely]]
fwrite(outBuf, 1, out - outBuf, stdout), out = outBuf;
if (!x) return *out++ = 48, void();
if (x < 0) *out++ = 45, x = -x;
alignas(2) const char* digits =
"0001020304050607080910111213141516171819"
"2021222324252627282930313233343536373839"
"4041424344454647484950515253545556575859"
"6061626364656667686970717273747576777879"
"8081828384858687888990919293949596979899";
alignas(64) static char buf[20];
char* p = buf + 20;
while (x >= 10) memcpy(p -= 2, digits + x % 100 * 2, 2), x /= 100;
if (x) *--p = 48 + x;
auto len = buf + 20 - p;
memcpy(out, p, len), out += len;
}
void init() {
in1 = in2 = inBuf + inSZ;
out = outBuf;
}
~IO() { fwrite(outBuf, 1, out - outBuf, stdout); }
} IO;
template<class T = int> inline T read() {
return IO.read<T>();
}
template<class... Args> inline void read(Args&... args) {
((args = IO.read<Args>()), ...);
}
template<class T> inline void write(T x, char c = '\n') {
IO.write(x), *IO.out++ = c;
}
constexpr int N = 2e6 + 5;
int n, q, a[N], ans[N]; vector<array<int, 2>> qq[N], Q[N], v[N];
int NN, t[(int)1e7 + 5];
inline void build() {
for (int i = 1; i <= n; i++) t[i + NN] = 0;
for (int i = NN; i; i--) t[i] = t[i << 1] + t[i << 1 | 1];
}
inline void upd(int p, int x) {
t[p + NN] = x;
for (int i = (p + NN) >> 1; i; i >>= 1) t[i] = max(t[i << 1], t[i << 1 | 1]);
}
inline int qry(int l, int r) {
int res = 0;
for (l += NN - 1, r += NN + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
if (~l & 1) res = max(res, t[l ^ 1]);
if (r & 1) res = max(res, t[r ^ 1]);
} return res;
}
set<int> s; unordered_map<int, vector<int>> mp, bucc;
inline void init() {
mp.clear();
rep (i, 1, n + 1) v[i].clear();
per (i, n, 1) {
v[i].push_back({i, a[i]}); mp[a[i]].push_back(n - i);
for (auto to : v[i + 1]) {
if ((to[1] | a[i]) ^ v[i].back()[1]) {
v[i].push_back({to[0], to[1] | a[i]});
mp[v[i].back()[1]].push_back(n - i);
if (v[i].back()[1] ^ to[1]) mp.erase(to[1]);
}
} v[i].push_back({n + 1, 0});
rep (p, 0, v[i].size() - 2) {
int l = v[i][p][0], r = v[i][p + 1][0] - 1;
if (a[l] ^ v[i][p][1]) {
vector<int> &st = bucc[v[i][p][1]];
auto it = upper_bound(st.begin(), st.end(), l);
if (it == st.end()) continue;
l = *it; if (l <= r) Q[l].push_back({1, i}), Q[r + 1].push_back({0, i});
continue;
}
vector<int> &st = mp[v[i][p][1]];
auto it = lower_bound(st.begin(), st.end(), n - l);
if (it == st.begin()) continue; it = prev(it);
for (auto to : v[n - *it]) if (to[1] == v[i][p][1]) {
l = to[0]; break;
}
if (l <= r) Q[l].push_back({1, i}), Q[r + 1].push_back({0, i});
}
v[i].pop_back();
}
}
inline void solve() {
n = read(), q = read(); bucc.clear();
rep (i, 1, n) {
a[i] = read(), bucc[a[i]].push_back(i);
qq[i].clear(), Q[i].clear();
}
rep (i, 1, q) {
int l = read(), r = read();
qq[r].push_back({l, i});
}
init(); NN = 1 << (__lg(n) + 1); build(), s.clear(); s.insert(n + 1);
rep (i, 1, n) {
sort(Q[i].begin(), Q[i].end());
for (auto [op, x] : Q[i]) {
if (op) s.insert(x);
else s.erase(x), upd(x, i - x);
}
for (auto [l, id] : qq[i]) {
ans[id] = max(qry(l, i), i - *s.lower_bound(l) + 1);
}
}
rep (i, 1, q) write(max(ans[i], 1));
}
signed main() {
IO.init();
int kowen = read(), opunt = read();
while (kowen--) solve();
return 0;
}