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

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

个人Limitの线段树题单题解主目录：Limitの线段树题单 题解目录_HeartFireY的博客-CSDN博客

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

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

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

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

题目分析

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

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

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

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

怎么会是黑题？假的吧。

Code

#include 
#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, mid
    #define rson rs, mid + 1, r

    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, n

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93