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\) 更优了。
然后这道题基本就结束了。
整理一下：
-
离线扫描线；
-
每扫到一个点，线段树上区间修改，然后更新并查集；
-
处理右端点再当前位置的查询，每个查询的 \(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';
}