看到值域比较，又支持离线，可以想到莫队和桶。
考虑先将桶按 \(b\) 分段，将每段分别进行按位与运算，做完第 \(i\) 段时用于运算的桶全都为 \(0\)，就可以直接得到答案。这显然可以用 bitset 优化。但是 STL 的 bitset 不支持分裂操作，所以需要手写。
当 \(b\) 较大时时间复杂度为 \(\mathcal{O}(n\sqrt{m} + m\dfrac{V}{b}\times\dfrac{b}{w})\)（不考虑排序）。
但是发现当 \(b < w\) 时时间复杂度是错的，此时就变为了 \(\mathcal{O}(n\sqrt{m} + m\dfrac{V}{b})\)，因为这时候小段太短了，bitset 的压位就失去了作用。
现在考虑 \(b < 64\) 的情况。
由于 \(b\) 很小，考虑对于每一个 \(b\in[1, w - 1])\) 做一遍莫队。
这时就只需在 \(\mod b\) 的位置加 \(1\)，即维护 \(b\) 剩余类。又发现 \(\mod b\) 的值较小，直接对每一个 \(i\) 维护其 \(\text{mex}\) 即可，最后的答案就是 \(\max\{\text{mex}\}\)，对于每一个 \(i\) 求 \(\text{mex}\)，依然可以用 bitset 优化。
这一部分的时间复杂度为 \(\mathcal{O}(\sum\limits_{i = 1}^{w - 1}(n\sqrt{cntq_i} + i\dfrac{V}{i}\times\dfrac{1}{w}))\)，由均值不等式 \(\dfrac{\sum\limits_{i = 1}^{n}a_i}{n}\le \sqrt{\dfrac{\sum\limits_{i = 1}^{n}a_i^2}{n}}\) 可得这部分的时间复杂度上界为 \(\mathcal{O}(n\times w\sqrt{\dfrac{\sum (\sqrt{cntq_i})^2}{w}} + V)\)，即 \(\mathcal{O}(n\sqrt{mw} + V)\)，其中的 \(\sqrt{w}\) 为常数。
时间复杂度：\(\mathcal{O}(n\sqrt{m} + \dfrac{mV}{w})\)
代码：
const int N = 1e5 + 10, V = 1e5 + 1, MOD = 63, W = 64, bit = 6;
int n, m, len, cq, nowb;
int a[N], cnt[N], ans[N];
ull filter[W];
struct que {
int l, r, b, id;
} q[N];
bool cmp(que a, que b) {
int x = a.l / len, y = b.l / len;
if (x == y) {
if (x & 1) return a.r < b.r;
return a.r > b.r;
}
return a.l < b.l;
}
vector<que> qb[W];
struct bitsett {
int siz;
vector<ull> v;
void reset() { for (int i = 0; i <= siz; i++) v[i] = 0; }
void set() { for (int i = 0; i <= siz; i++) v[i] = ~0ull; }
void set1(int x) { v[x >> bit] |= (1ull << (x & MOD)); }
void set0(int x) { v[x >> bit] &= (~(1ull << (x & MOD))); }
void flip() { for (int i = 0; i <= siz; i++) v[i] = ~v[i]; }
void operator &= (const bitsett &a) { for (int i = 0; i <= siz; i++) v[i] &= a.v[i]; }
int mex() { for (int i = 0; ; i++) if (~v[i]) return i << bit | __builtin_ctzll(~v[i]); }
void init(int x) {
v.resize((x >> bit) + 2);
siz = x >> bit;
reset();
}
bool any() {
for (int i = 0; i <= siz; i++) if (v[i]) return 1;
return 0;
}
};
bitsett cur, res, bl[1605], blb[W + 5];
void split(int len) {
for (int i = 0; i <= V / len + 2; i++) bl[i].init(len);
int ned = bl[0].siz, bg = 0, np = 0, num = 0;
for (int i = 0; i <= cur.siz; i++)
if (np == ned) {
if (bg + (len & MOD) <= MOD) {
bl[num].v[np] = (cur.v[i] & (filter[bg + (len & MOD) - 1] - (bg ? filter[bg - 1] : 0))) >> bg;
i--;
}
else if (i != cur.siz) {
bl[num].v[np] = (cur.v[i] >> bg) | ((cur.v[i + 1] & filter[bg + (len & MOD) - MOD]) << (W - bg));
} else
bl[num].v[np] = (cur.v[i] >> bg);
bg = (bg + (len & MOD)) & MOD, np = 0, num++;
} else {
if (bg == 0) bl[num].v[np] = cur.v[i];
else if (i != cur.siz) bl[num].v[np] = (cur.v[i] >> bg) | ((cur.v[i + 1] & filter[bg - 1]) << (W - bg));
else bl[num].v[np] = cur.v[i] >> bg;
np++;
}
}
void add1(int x) {
cnt[x]++;
if (cnt[x] == 1) cur.set1(x);
}
void del1(int x) {
cnt[x]--;
if (cnt[x] == 0) cur.set0(x);
}
void add2(int x) {
cnt[x]++;
if (cnt[x] == 1) blb[x % nowb].set1(x / nowb);
}
void del2(int x) {
cnt[x]--;
if (cnt[x] == 0) blb[x % nowb].set0(x / nowb);
}
int main() {
filter[0] = 1;
for (int i = 1; i < W; i++) filter[i] = filter[i - 1] + (1ull << i);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> m;
for (int i = 1, l, r, b; i <= m; i++) {
cin >> l >> r >> b;
if (b > 63) q[++cq] = (que){l, r, b, i};
else qb[b].pb((que){l, r, 0, i});
}
len = n / sqrt(cq) + 1;
sort(q + 1, q + cq + 1, cmp);
cur.init(V);
for (int i = 1, l = 1, r = 0; i <= cq; i++) {
while (l > q[i].l) add1(a[--l]);
while (r < q[i].r) add1(a[++r]);
while (l < q[i].l) del1(a[l++]);
while (r > q[i].r) del1(a[r--]);
split(q[i].b);
res.init(q[i].b);
res.flip();
for (int j = 0; ; j++) {
res &= bl[j];
if (!res.any()) {
ans[q[i].id] = j;
break;
}
}
}
int mxb = 63;
for (int i = 1; i <= mxb; i++) {
if (qb[i].size() == 0) continue;
memset(cnt, 0, sizeof(cnt));
nowb = i;
len = n / sqrt(qb[i].size()) + 1;
sort(qb[i].begin(), qb[i].end(), cmp);
for (int j = 0; j < i; j++) blb[j].init(V / i + 1);
for (int j = 0, l = 1, r = 0; j < (int)(qb[i].size()); j++) {
while (l > qb[i][j].l) add2(a[--l]);
while (r < qb[i][j].r) add2(a[++r]);
while (l < qb[i][j].l) del2(a[l++]);
while (r > qb[i][j].r) del2(a[r--]);
for (int k = 0; k < i; k++)
ans[qb[i][j].id] = max(ans[qb[i][j].id], blb[k].mex());
}
}
for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
return 0;
}