题意
给定长为 \(n\) 的序列，\(q\) 次询问区间 \([l, r]\) 的最短区间 \([l', r']\), 满足所有在 \([l, r]\) 中出现的数也在 \([l', r']\) 中出现，你只需要输出 \([l', r']\) 的长度即可。
Sol
离线，然后枚举 \(r\)。
考虑维护一个前缀的弱化版询问。
设 \([l, p_i]\) 为满足当前区间 \([l, r]\) 的最小的 \(p_i\)
用区间覆盖的线段树简单维护即可。
考虑如何算答案。
显然我们要求一个最大的 \(q\) 使得 \([q, r]\) 满足当前 \([l, r]\)。
不难发现 \(q=min(max (i\in a_i))\)。
这个东西可以用一个 \(set\) 简单维护，显然爆T。
考虑当前每一个 \(a_i\) 对于当前的 \(q\) 的贡献。
若当前移动到了 \(r\)，那么 \(lst[a[r]]\) 对 \(q\) 就没有任何贡献了。
建出并查集维护即可。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <set>
#define pii pair <int, int>
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;
#endif
int read() {
int p = 0, flg = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') flg = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
p = p * 10 + c - '0';
c = getchar();
}
return p * flg;
}
void write(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
#define fi first
#define se second
const int N = 2e6 + 5, inf = 1e9;
array <int, N> s;
array <pair <pii, int>, N> qs;
namespace Sgt {
array <int, 4 * N> edge, tag;
void pushup(int x) {
edge[x] = min(edge[x * 2], edge[x * 2 + 1]);
}
void pushdown(int x, int l, int r) {
if (!tag[x]) return;
int mid = (l + r) >> 1;
tag[x * 2] = tag[x];
tag[x * 2 + 1] = tag[x];
edge[x * 2] = tag[x] - mid + 1;
edge[x * 2 + 1] = tag[x] - r + 1;
tag[x] = 0;
}
void build(int x, int l, int r) {
edge[x] = inf;
if (l == r) return;
int mid = (l + r) >> 1;
build(x * 2, l, mid);
build(x * 2 + 1, mid + 1, r);
}
void modify(int x, int l, int r, int L, int R, int y) {
if (L > r || R < l) return;
if (L <= l && R >= r) {
edge[x] = y - r + 1;
tag[x] = y;
return;
}
pushdown(x, l, r);
int mid = (l + r) >> 1;
if (L <= mid) modify(x * 2, l, mid, L, R, y);
if (R > mid) modify(x * 2 + 1, mid + 1, r, L, R, y);
pushup(x);
}
int query(int x, int l, int r, int L, int R) {
if (L > r || R < l) return inf;
if (L <= l && R >= r) return edge[x];
pushdown(x, l, r);
int mid = (l + r) >> 1, ans = inf;
if (L <= mid) ans = min(ans, query(x * 2, l, mid, L, R));
if (R > mid) ans = min(ans, query(x * 2 + 1, mid + 1, r, L, R));
return ans;
}
}
using namespace Sgt;
array <int, N> lst, ans;
multiset <int> isl;
namespace Uni {
array <int, N> fa;
int find(int x) {
if (x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
void init(int n) {
for (int i = 1; i <= n; i++)
fa[i] = i;
}
}
using namespace Uni;
int main() {
int n = read();
for (int i = 1; i <= n; i++)
s[i] = read();
init(n);
int m = read();
for (int i = 1; i <= m; i++)
qs[i].fi.fi = read(), qs[i].fi.se = read(), qs[i].se = i;
build(1, 1, n);
sort(qs.begin() + 1, qs.begin() + 1 + m,
[](pair <pii, int> x, pair <pii, int> y) {
return x.fi.se == y.fi.se ? x.fi.fi < y.fi.fi : x.fi.se < y.fi.se;
});
int tp = 0;
for (int i = 1; i <= n; i++) {
/* write(i), puts(""); */
modify(1, 1, n, lst[s[i]] + 1, i, i);
if (lst[s[i]]) fa[lst[s[i]]] = lst[s[i]] + 1;
lst[s[i]] = i;
while (qs[tp + 1].fi.se <= i && tp < m) {
tp++;
int pos = find(qs[tp].fi.fi);
/* int pos = *isl.lower_bound(qs[tp].fi.fi); */
/* if (tp == 3) */
/* write(pos), puts("@"); */
ans[qs[tp].se] = query(1, 1, n, qs[tp].fi.fi, pos);
}
}
for (int i = 1; i <= m; i++)
write(ans[i]), puts("");
return 0;
}