11.CF522D Closest Equals 线段树+离线询问

11.CF522D Closest Equals 线段树+离线询问

给定序列，查询区间内距离最近的两个相等元素。

离线查询，按右端点加入贡献计算答案即可

洛谷传送门：​​CF522D Closest Equals - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)​​

CF传送门：​​D. Closest Equals (codeforces.com)​​

题目分析

给定序列，查询区间内距离最近的两个相等元素。

此类涉及元素相等的问题，一般是维护每个元素上次出现的位置。

首先，我们可以对所有询问进行离线。然后按照右端点排序后开始加入贡献(与上次出现的距离)。然后固定右端点查询即可：

记录 表示在 中跟 相同最近的位置。考虑离线，把询问按右端点排序，如果 就把 的位置修改为 ，然后就是区间求最小值了，注意到数据范围很大，需要进行离散化。

怎么会是黑题？假的吧。

Code

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 5e5 + 10, MOD = 1e9 + 7;
int a[N], b[N];

namespace ffastIO {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}

namespace SegTree{
    #define ls lc[rt]
    #define rs rc[rt]
    #define lson ls, l,
    #define rson rs, mid + 1,

    int lc[N << 2], rc[N << 2], tree[N << 2], tot;

    void build(){ memset(tree, 0x3f, sizeof(tree)); }

    void update(int &rt, int l, int r, int pos, int val){
        if(!rt) rt = ++tot;
        if(l == r) return (void)(tree[rt] = val);
        int mid = l + r >> 1;
        if(mid >= pos) update(lson, pos, val);
        else update(rson, pos, val);
        tree[rt] = min(tree[ls], tree[rs]);
    }

    int query(int rt, int l, int r, int L, int R){
        if(l >= L && r <= R) return tree[rt];
        int mid = l + r >> 1, ans = 1e16;
        if(mid >= L) ans = min(ans, query(lson, L, R));
        if(mid < R) ans = min(ans, query(rson, L, R));
        return ans;
    }

}

struct info{ int id, l; };

vector<info> q[N];
int ans[N], pre[N], lst[N];

using ffastIO::read;
using SegTree::query;
using SegTree::update;

#define SEGRG root, 1,

inline void solve(){
    SegTree::build();
    int n = read(), m = read(), root = 0;
    for(int i = 1; i <= n; i++) a[i] = b[i] = read();
    sort(b + 1, b + 1 + n);
    int n1 = unique(b + 1, b + 1 + n) - (b + 1);
    auto get = [&](int x) { return lower_bound(b + 1, b + 1 + n1, x) - b; };
    for(int i = 1; i <= n; i++){
        a[i] = get(a[i]);
        pre[i] = lst[a[i]], lst[a[i]] = i;
    }
    for(int i = 1; i <= m; i++){
        int l = read(), r = read();
        q[r].emplace_back(info{i, l});
    }

    for(int i = 1; i <= n; i++){
        if(pre[i]) update(SEGRG, pre[i], i - pre[i]);
        for(auto qu : q[i]) ans[qu.id] = query(SEGRG, qu.l, i);
    }

    for(int i = 1; i <= m; i++) cout << (ans[i] > 1000000 ? -1 : ans[i]) << endl;
}

signed main(){
    solve();
    return 0;
}