Closest Equals

Closest Equals

#includeusing namespace std;#define rep(i,l,r) for(int i=(l);i<=(r);i++)#define per(i,l,r) for(int i=(l);i>=(r);i--)#define ll long long#define mset(s,t) memset(s,t,sizeof(t))#define mcpy(s,t) memcpy(s,t,sizeof(t))#define fi first#define se second#define pb push_back#define all(x) (x).begin(),(x).end()#define SZ(x) ((int)(x).size())#define mp make_pairtypedef pair pii;typedef pair pll;typedef vector vi; typedef vector Vll; typedef vector > vpii;typedef vector > vpll; const ll mod = 1e9 + 7;//const ll mod = 998244353;const double pi = acos(-1.0);inline ll qmi (ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans = ans * a%mod; a = a * a %mod; b >>= 1; } return ans;}inline int read () { int x = 0, f = 0; char ch = getchar(); while (!isdigit(ch)) f |= (ch=='-'),ch= getchar(); while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return f?-x:x;}template void print(T x) { if (x < 0) putchar('-'), x = -x; if (x >= 10) print(x/10); putchar(x % 10 + '0');}inline ll sub (ll a, ll b) { return ((a - b ) %mod + mod) %mod;}inline ll add (ll a, ll b) { return (a + b) %mod;}inline ll inv (ll a) { return qmi(a, mod - 2);}const int N = 4e6 +10;struct Node { int l, r; int id;}query[N];int n, m;int a[N];struct Tree { int l, r; int minv;}t[N];int ans[N];void build (int p, int l, int r) { t[p].l = l, t[p].r = r; if (l == r) { t[p].minv = 1e9; return; } int mid = l + r >> 1; build(p * 2, l, mid); build(p * 2 + 1, mid + 1, r); t[p].minv = min (t[p * 2].minv, t[p * 2 + 1].minv);}int ask (int p, int l, int r) { if (t[p].l >= l && t[p].r <= r) { return t[p].minv; } int mid = t[p].l + t[p].r >> 1; int val = 1e9; if (l <= mid) val = min (val, ask(p * 2, l, r)); if (r > mid) val = min (val, ask(p * 2 + 1, l, r)); return val;}void update (int p, int x, int v) { if (t[p].l == t[p].r) { t[p].minv = v; return; } int mid = t[p].l + t[p].r >> 1; if (x <= mid) update(p * 2, x, v); else update(2 * p + 1, x, v); t[p].minv =min (t[p * 2].minv, t[p * 2 + 1].minv);}void solve() { cin >> n >> m; rep(i, 1, n) { a[i] = read(); } for (int i = 1; i <= m; i ++) { query[i].l = read(); query[i].r = read(); query[i].id = i; } sort(query + 1, query + 1 + m, [&](Node a, Node b) { return a.r < b.r; }); map last; int pos = 1; build(1, 1, n); for (int i = 1; i <= m; i ++) { while (pos <= query[i].r) { if (last[a[pos]]) update(1, (last[a[pos]]), pos - last[a[pos]]); last[a[pos]] = pos; pos ++; } ans[query[i].id] = ask(1, query[i].l, query[i].r); } for (int i = 1; i <= m; i ++) { if (ans[i] == 1e9) ans[i] = -1; printf("%d\n", ans[i]); } puts("");}int main () { // ios::sync_with_stdio(0),cin.tie(0), cout.tie(0); int t; t =1; //cin >> t; while (t --) solve(); return 0;}

题意:给你一个长为n的数组，每个查询问区间[l, r]相同的两个数相隔最近是多少 线段树离线操作 用map维护最近距离。对于一个数，我们先将查询按照右端点，排成升序。然后对于一个查询，我们先将[1, r]全部插入，然后查询。每一个位置只被插入一次。因此整个算法是O(nlon)的 想到了用线段树，但是没有想到查什么。这里是通过map维护一个答案

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。