离线查询+线段树，CF522D - Closest Equals

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

522D - Closest Equals

---

二、解题报告

1、思路分析

考虑查询区间已经给出，我们可以离线查询

对于这类区间离线查询的问题我们通常可以通过左端点排序，然后遍历询问同时维护左区间信息来完成

我们考虑可以预处理出d[], d[i]代表a[i]和其左边最近的相等的值的距离，如果没有就置为n

然后线段树维护区间最值

预处理nxt[i]即a[i]下一个出现位置

考虑将询问按照左端点升序排序

遍历查询q，如果当前遍历到的l < q[i].l，我们就右扩展左区间，同时modify nxt[l]为正无穷

然后查询区间[l, r]的最值即可

2、复杂度

时间复杂度： O(NlogN + MlogN)空间复杂度：O(N)

3、代码详解

 ​

#include <bits/stdc++.h>
using i64 = long long;
using i128 = __int128;
using PII = std::pair<int, int>;
const int inf = 1e9 + 7, P = 1e9 + 7;template<class Info>
struct SegmentTree {int n;std::vector<Info> info;SegmentTree(int _n): n(_n), info(2 << (32 - __builtin_clz(_n))) {}SegmentTree(std::vector<Info>& _init): SegmentTree(_init.size()) {auto build = [&](auto&& self, int p, int l, int r) {if (l == r) {info[p] = _init[l];return;}int mid = l + r >> 1;self(self, p << 1, l, mid), self(self, p << 1 | 1, mid + 1, r);pull(p);};build(build, 1, 0, n - 1);}void pull(int p) {info[p] = info[p << 1] + info[p << 1 | 1];}void modify(int p, int l, int r, int x, const Info& v) {if (l == r) {info[p] = v;return;}int mid = l + r >> 1;if (x <= mid) modify(p << 1, l, mid, x, v);else modify(p << 1 | 1, mid + 1, r, x, v);pull(p);}void modify(int x, const Info& v) {modify(1, 0, n - 1, x, v);}Info rangeQuery(int p, int l, int r, int x, int y) {if (l > y || r < x) return Info();if (x <= l && r <= y) return info[p];int mid = l + r >> 1;return rangeQuery(p << 1, l, mid, x, y) + rangeQuery(p << 1 | 1, mid + 1, r, x, y);}Info rangeQuery(int l, int r) {return rangeQuery(1, 0, n - 1, l, r);}};
struct Info {int x = inf;Info operator + (const Info& b) const {return  { std::min(x, b.x) };}
};void solve() {int n, m;std::cin >> n >> m;std::vector<int> a(n), nxt(n, n);std::map<int, int> last;for (int i = 0; i < n; i ++ ) {std::cin >> a[i];if (last.count(a[i]))nxt[last[a[i]]] = i;last[a[i]] = i;}std::vector<Info> d(n);for (int i = 0; i < n; i ++ )if (nxt[i] < n) d[nxt[i]] = { nxt[i] - i };SegmentTree<Info> sgt(d);std::vector<std::array<int, 3>> q(m);std::vector<int> ans(m);for (int i = 0, l, r; i < m; i ++ ) std::cin >> l >> r, q[i] = { l, r, i };std::sort(q.begin(), q.end(), [](auto& x, auto& y) {return x[0] < y[0];});for (int i = 0, st = 0; i < m; i ++ ) {auto [l, r, id] = q[i];-- l, -- r;while (st < l) {if (nxt[st] < n)sgt.modify(nxt[st], Info());++ st;}ans[id] = sgt.rangeQuery(l, r).x;}for (int x : ans) std::cout << (x < inf ? x : -1) << '\n';
}int main(int argc, char** argv) {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int _ = 1;// std::cin >> _;while (_ --)solve();return 0;
}