P4137题解

传送门：https://www.luogu.com.cn/problem/P4137

对于某一个值判断是否在 \([L,R]\)。因为是值域问题，考虑主席树维护当前位置值域，一种方法是维护每种数的出现次数。但题目要求mex不可避免的是枚举每个点做值域差分判断是否存在。我们需要寻找一种可以整体快速判断是否存在的点信息。最值便是一种。值域中每个点储存该值在当前右端点版本的序列中出现的最右位置。当一个值域区间的某个值出现最右位置的小于 \(l\) 时，mex就在该区间内。通过维护区间最小值然后在可持久化线段树上二分即可。因为不强制在线，又因为查询时只需要当前版本的线段树信息，离线后普通线段树即可，因为二分是全局的只需要每次简单往左端点找。

#include <bits/stdc++.h>const int N = 2e5 + 1;using namespace std;struct Query {int l, r, ans, id;bool operator <(const Query &o) const { return id < o.id; }
} q[N];bool cmp(Query q1, Query q2) { return q1.r < q2.r; }int a[N], Min[N << 2];int ls(int p) { return p << 1; }int rs(int p) { return p << 1 | 1; }void pushup(int p) { Min[p] = min(Min[ls(p)], Min[rs(p)]); }void update(int p, int lp, int rp, int pos, int val) {if (lp == rp) {Min[p] = val;return;}int mid = (lp + rp) >> 1;if (pos <= mid) update(ls(p), lp, mid, pos, val);else update(rs(p), mid + 1, rp, pos, val);pushup(p);
}int query(int p, int lp, int rp, int l) {if (lp == rp) return lp;int mid = (lp + rp) >> 1;if (Min[ls(p)] < l) return query(ls(p), lp, mid, l);return query(rs(p), mid + 1, rp, l);
}int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n, m, V = 2e5 + 1;cin >> n >> m;for (int i = 1; i <= n; ++i) cin >> a[i];for (int i = 1; i <= m; ++i) cin >> q[i].l >> q[i].r, q[i].id = i;sort(q + 1, q + m + 1, cmp);int now = 1;for (int i = 1; i <= m; ++i) {while (now <= n && now <= q[i].r) update(1, 0, V, a[now], now), ++now;q[i].ans = query(1, 0, V, q[i].l);}sort(q + 1, q + m + 1);for (int i = 1; i <= m; ++i) cout << q[i].ans << '\n';return 0;
}