526互联

P7907 [Ynoi2005] rmscne 题解

发布时间 2023-11-18 21:32:29作者: 流星Meteor

P7907 [Ynoi2005] rmscne 题解

退役前的最后一篇题解，献给 Ynoi。再见了各位。

题目大意

给定一个长度为 \(n\) 的序列和 \(m\) 次查询，对于每次查询，给定 \(l, r\)，求出一个最短的子区间 \([l', r']\)，满足所有在区间 \([l, r]\) 中出现的数也在 \([l',r']\) 中出现过。

题解

题还是很好的。我讲的尽量细一点。

由于题解里所述的 \(q\) 与原题面重了，所以我们将原题面里的 \(q\) 次查询改成 \(m\) 次查询。

\(1 \le n, m \le 2 \times 10^6, 3s, 512 MB\)

先设一个东西：

\(S_{l, r}\) 表示区间 \([l, r]\) 里所有的数构成的集合。那么原题目的限制条件就可以转化为 \(S_{l, r} = S_{l', r'}\)。

没说强制在线，然后还是区间查询，那就考虑离线扫描线。

每扫到一个位置，处理右端点在这个位置的所有查询。

先来考虑简化版的问题：

给你一个区间 \([l, r]\) ，查询最短的满足 \(S_{l, r} = S_{l', r'}\) 的子区间 \([l', r']\) 的长度。

对于这个简化版问题，我们可以对每一个位置，维护左端点 \(l'\) 在这个位置时，最小的右端点 \(r'\) 以及其区间长度。但是我们发现，以某一些位置为左端点时，找不到对应的右端点，我们现在设法除去这些区间的干扰，不把它们算在答案的考虑范围之内，这方便我们一会儿解决原问题。设 \([q, r]\) 是以 \(r\) 为 \(r'\) 时，最短的满足条件的子区间。不难发现，将 \(i (i \in (q, r])\) 作为左端点 \(l'\) 时，是没有对应的右端点 \(r'\) 的。所以这个简化版问题的答案就是左端点为 \(i (i \in [l, q])\) 时，最短的区间长度。这个东西很线段树，不是么？

我们再来考虑原问题。

线段树维护对于一个点 \(i\)，满足 \(S_{i, p} = S_{i, r}\)（\(r\) 为当前扫到的位置）的最小的 \(p\)。但是我们不需要这个 \(p\)，我们只需要维护 \(p - i + 1\)，即区间长度。

那么我们在处理区间 \([l, r]\) 的答案时，就是线段树上 \([l, q]\) 的最小值（\(q\) 就是上文所述的东西，即 \([q, r]\) 是以 \(r\) 为 \(r'\) 时，最短的满足条件的子区间）。

考虑这样求答案的正确性。

根据 \(q\) 的定义，\(S_{q, r} = S_{l, r}\)，所以限制条件就可以转化成 \(S_{l', r'} = S_{l, r} = S_{q, r}\)。对于区间 \([l, q]\) 里的每一个 \(i\)，\(S_{i, r} = S_{q, r}\) 这个条件一定满足，而对于区间 \((q, r]\) 里的每一个 \(i\)，\(S_{i, r} = S_{q, r}\) 这个条件一定不满足（因为在位置 \(q\) 上的数，一定在 \(S_{q, r}\) 仅出现过一次，否则不优，\(q\) 可以更大）。

证毕。

所以我们现在的问题就转化成了，对于每一个 \(r\)，求出对应的 \(q\)，然后直接在线段树上查询即可。

查询就没了，现在讲修改。

考虑现在新扫到了一个位置 \(r + 1\)，这个位置上的数为 \(a_{r + 1}\)，我们记它上一次出现的位置为 \(lst\)，那么对于区间 \([1, lst]\) 里的每一个 \(i\)，\(S_{i, r} = S_{i, r + 1}\)，不需要进行什么修改，而对于区间 \([lst + 1, r + 1]\) 里的每一个 \(i\)，\(S_{i, r} \not= S_{i, r + 1}\)，所以满足 \(S_{i, p} = S_{i, r}\) 的最小的 \(p\) 一定需要更新成 \(r + 1\)。

所以线段树部分就没了，就是一颗支持区间修改，区间最值查询的线段树，比较平凡。

我们考虑现在的复杂度是什么。

一共会进行 \(n\) 次修改，每次修改 \(O(\log n)\)；一共有 \(m\) 次查询，每次查询需要找到一个 \(q\)（现在我们先二分找到这个 \(q\)，一会儿再优化），然后再在线段树上查询，单次 \(O(\log n)\)。总的复杂度是 \(O(n \log n)\)，但是常数似乎不小，过不去。

考虑优化。

考虑怎么对于每一个 \(r\) 迅速找到一个 \(q\)。

一个不太好想的优化，反正我没想到，看题解想到的。

考虑并查集优化，对于一个位置 \(i\)，它的祖先就是，如果以这个点作为 \(q\)，那么更优的 \(q\) 的位置，或者说我们先假定 \(i\) 为 \(q\)，但是我们发现这个位置不优，于是它的祖先就指向了一个更优的位置。每一次新扫到一个位置 \(r + 1\)，这个位置上的数为 \(a_{r + 1}\)，我们记它上一次出现的位置为 \(lst\)，那么我们将位置 \(lst\) 的祖先更新成 \(lst + 1\) 即可。我们最终用的 \(q\) 就是 \(l\) 位置的祖先。

为什么这么更新？

因为如果 \(q\) 在位置 \(lst\) 上，当前数与位置 \(lst\) 上的数相同，所以 \(lst\) 位置就没有用了，所以 \(lst + 1\) 就比 \(lst\) 更优了。

然后这道题基本就结束了。

整理一下：

  1. 离线扫描线；

  2. 每扫到一个点，线段树上区间修改，然后更新并查集；

  3. 处理右端点再当前位置的查询，每个查询的 \(q\) 就是 \(l\) 的祖先。

代码

#include <bits/stdc++.h>
#define P pair<int, int>
#define MP make_pair
using namespace std;

const int M = 2000005;
int n, q, a[M], ans[M], fa[M], lst[M];
int minn[M << 2], lazy[M << 2];
vector<P> vec[M];

inline int findf(int x) {
    while(x != fa[x]) 
        x = fa[x] = fa[fa[x]];
    return x;
}

inline void push_down(int rt, int l, int r) {
    if(lazy[rt]) {
        int mid = (l + r) >> 1, ls = rt << 1, rs = ls | 1;
        minn[ls] = lazy[rt] - mid + 1;
        minn[rs] = lazy[rt] - r + 1;
        lazy[ls] = lazy[rt];
        lazy[rs] = lazy[rt];
        lazy[rt] = 0;
    }
}

inline void push_up(int rt) {
    int ls = rt << 1, rs = ls | 1;
    minn[rt] = min(minn[ls], minn[rs]);
}

void build(int rt, int l, int r) {
    minn[rt] = INT_MAX;
    lazy[rt] = 0;
    if(l == r) 
        return;
    int mid = (l + r) >> 1, ls = rt << 1, rs = ls | 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
}

void change(int rt, int l, int r, int zuo, int you, int addend) {
    if(zuo <= l && r <= you) {
        minn[rt] = addend - r + 1;
        lazy[rt] = addend;
        return;
    }
    push_down(rt, l, r);
    int mid = (l + r) >> 1, ls = rt << 1, rs = ls | 1;
    if(zuo <= mid)
        change(ls, l, mid, zuo, you, addend);
    if(you > mid)
        change(rs, mid + 1, r, zuo, you, addend);
    push_up(rt);
}

int ask(int rt, int l, int r, int zuo, int you) {
    if(zuo <= l && r <= you) 
        return minn[rt];
    push_down(rt, l, r);
    int mid = (l + r) >> 1, ls = rt << 1, rs = ls | 1, res = INT_MAX;
    if(zuo <= mid)
        res = ask(ls, l, mid, zuo, you);
    if(you > mid)
        res = min(res, ask(rs, mid + 1, r, zuo, you));
    push_up(rt);
    return res;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    build(1, 1, n);
    for(int i = 1; i <= n; ++ i) 
        cin >> a[i], fa[i] = i;
    cin >> q;
    for(int i = 1; i <= q; ++ i) {
        int l, r;
        cin >> l >> r;
        vec[r].push_back(MP(l, i));
    }
    for(int i = 1; i <= n; ++ i) {
        fa[lst[a[i]]] = lst[a[i]] + 1;
        change(1, 1, n, lst[a[i]] + 1, i, i);
        for(int j = 0; j < vec[i].size(); ++ j) 
            ans[vec[i][j].second] = ask(1, 1, n, vec[i][j].first, fa[findf(vec[i][j].first)]);
        lst[a[i]] = i;
    }
    for(int i = 1; i <= q; ++ i) 
        cout << ans[i] << '\n';
}