题目描述
思路
题意： 给定一个数组，多次询问区间 [ l , r ]中相同的数的间隔的最小值。
首先拿到题目第一想法就是考虑，如何维护一个区间相同的数的间距最小值。似乎很熟悉，我们可以用线段树去维护一段区间的最小值信息。那么我们可以开数组 a aa，用来存储不同位置下，和前一位值相同的数的间距。然后我们的线段树就去维护的是数组 a aa，每次查询就返回区间的最小值即可。
但是存在这种情况： 当前询问的区间中，a i 值是最小的，但是 i 这一位对应值，它的前一位相同值并不在区间范围内。也就是说，对于这个询问来说 a i是不能产生贡献的。所以可以将其赋值为一个极大值，这也就需要线段树的单点修改操作。
那么考虑完上面的情况，我们发现如果是这样执行，每次对一个询问区间，我们需要遍历一次区间，把不应该产生贡献的值都给修改掉，并且考虑到当前修改的点，可能对后续的询问产生影响，那么我们还需要在修改回来。这样的时间复杂度是不可以接受的。所以我们实现的过程中，可以将询问进行离线。对询问的区间进行左端点排序。那么在询问完当前区间，在询问下一个区间时，两次询问的左端点之间的数，是不会在有询问的，所以其对后续的询问点的影响需要清空掉。
那么如何清空这些无用点的影响呢？
考虑到这个点对后续的影响是，在询问区间中的点，也就是下一位。所以我们可以开一个 b bb 数组，用于存储每个点它的对应的值的下一位在哪个位置。在修改的时候只需要跳到下一个位置进行修改即可。
代码
struct node { int l, r; int id; bool operator<(const node &A) const { if (l == A.l) return r < A.r; return l < A.l; } } q[N]; int idx; int n, m; map<int, int> mp; int a[N], b[N]; struct Node { int l, r; int v; } tr[N << 2]; #define ls u<<1 #define rs u<<1|1 #define INF 2e9 void pushup(int u) { tr[u].v = min(tr[ls].v, tr[rs].v); } void build(int u, int l, int r) { tr[u] = {l, r}; if (l == r) { tr[u].v = a[l]; return ; } int mid = l + r >> 1; build(ls, l, mid), build(rs, mid + 1, r); pushup(u); } int query(int u, int l, int r) { if (tr[u].l >= l && tr[u].r <= r) return tr[u].v; int mid = tr[u].l + tr[u].r >> 1; int res = INF; if (l <= mid) res = min(res, query(ls, l, r)); if (r > mid) res = min(res, query(rs, l, r)); return res; } void modify(int u, int x) { if (tr[u].l >= x && tr[u].r <= x) { tr[u].v = INF; return ; } int mid = tr[u].l + tr[u].r >> 1; if (x <= mid) modify(ls, x); else modify(rs, x); pushup(u); return ; } int res[N]; // https://codeforces.com/contest/522/problem/D void solve() { cin >> n >> m; for (int i = 1; i <= n; i++) a[i] = b[i] = INF; for (int i = 1; i <= n; i++) { int x; cin >> x; if (mp.count(x)) { a[i] = i - mp[x]; b[mp[x]] = i; } mp[x] = i; } for (int i = 1; i <= m; i++) { int l, r; cin >> l >> r; q[i] = {l, r}; q[i].id = i; } sort(q + 1, q + 1 + m); build(1, 1, n); q[m + 1].l = -1; for (int i = 1; i <= m; i++) { int l = q[i].l, r = q[i].r; res[q[i].id] = query(1, l, r); for (int p = l; p < q[i + 1].l; p++) { if(b[p] <= n) modify(1, b[p]); } } for (int i = 1; i <= m; i++) { if (res[i] >= INF) res[i] = -1; cout << res[i] << endl; } }
