区间 mex 的刻画手法
stripe_python · · 算法·理论
定义 对非负整数序列
定理 1 若
证明 设
定理表明,排列的区间 mex 等价于前后缀 min 合并。
问题 1 给定长为
显然
离线对
从而
复杂度
:::::info[代码]
const int N = 2e5 + 5;
int n, q, a[N];
// 在线询问,可持久化线段树
int tot, T[N], lc[30*N], rc[30*N], val[30*N];
#define ls lc[rt]
#define rs rc[rt]
void pushup(int rt) {val[rt] = min(val[ls], val[rs]);}
int clone(int rt) {
int u = ++tot;
return lc[u] = ls, rc[u] = rs, val[u] = val[rt], u;
}
int insert(int x, int c, int l, int r, int rt) {
int u = clone(rt);
if (l == r) return val[u] = c, u;
int mid = (l + r) >> 1;
if (x <= mid) lc[u] = insert(x, c, l, mid, ls);
else rc[u] = insert(x, c, mid + 1, r, rs);
return pushup(u), u;
}
int ask(int x, int l, int r, int rt) {
if (l == r) return l;
int mid = (l + r) >> 1;
return val[ls] < x ? ask(x, l, mid, ls) : ask(x, mid + 1, r, rs);
}
void _main() {
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) T[i] = insert(a[i], i, 0, n+1, T[i-1]);
for (int l, r; q--; ) {
cin >> l >> r;
cout << ask(l, 0, n+1, T[r]) << '\n';
}
}
:::::
问题 2 给定长为
取数值
取所有
使用树状数组套动态开点线段树维护二维平面,复杂度
注意特判
:::::info[代码]
const int N = 5e5 + 5, inf = 1e9;
int n, q, a[N], ls[N];
set<int> pos[N];
struct BIT {
int tot, lc[80*N], rc[80*N], val[80*N];
BIT() {val[0] = inf;}
#define ls lc[rt]
#define rs rc[rt]
void pushup(int rt) {val[rt] = min(val[ls], val[rs]);}
int create() {
int u = ++tot;
return lc[u] = rc[u] = 0, val[u] = inf, u;
}
void update(int y, int v, int l, int r, int& rt) {
if (!rt) rt = create();
if (l == r) return val[rt] = v, void();
int mid = (l + r) >> 1;
if (y <= mid) update(y, v, l, mid, ls);
else update(y, v, mid + 1, r, rs);
pushup(rt);
}
int ask(int tl, int tr, int l, int r, int rt) {
if (!rt) return inf;
if (tl <= l && r <= tr) return val[rt];
int mid = (l + r) >> 1, res = inf;
if (tl <= mid) chkmin(res, ask(tl, tr, l, mid, ls));
if (tr > mid) chkmin(res, ask(tl, tr, mid + 1, r, rs));
return res;
}
int T[N];
void modify(int x, int y, int v) {
for (; x <= n; x += lowbit(x)) update(y, v, 1, n, T[x]);
}
int ask(int x, int y) {
int res = inf;
for (; x >= 1; x -= lowbit(x)) chkmin(res, ask(y, n, 1, n, T[x]));
return res;
}
#undef ls
#undef rs
} B;
struct segtree {
#define ls (rt << 1)
#define rs (rt << 1 | 1)
int mx[4*N], mn[4*N];
void pushup(int rt) {mx[rt] = max(mx[ls], mx[rs]), mn[rt] = min(mn[ls], mn[rs]);}
void build(int l = 0, int r = n+1, int rt = 1) {
if (l == r) return setval(l, rt), void();
int mid = (l + r) >> 1;
build(l, mid, ls), build(mid + 1, r, rs), pushup(rt);
}
void setval(int x, int rt) {
if (pos[x].size() > 2) mx[rt] = *next(pos[x].begin()), mn[rt] = *next(pos[x].rbegin());
else mx[rt] = n+1, mn[rt] = 0;
}
void update(int x, int l = 0, int r = n+1, int rt = 1) {
if (l == r) return setval(x, rt), void();
int mid = (l + r) >> 1;
if (x <= mid) update(x, l, mid, ls);
else update(x, mid + 1, r, rs);
pushup(rt);
}
int ask1(int x, int l = 0, int r = n+1, int rt = 1) {
if (mx[rt] <= x) return inf;
if (l == r) return l;
int mid = (l + r) >> 1;
return mx[ls] > x ? ask1(x, l, mid, ls) : ask1(x, mid + 1, r, rs);
}
int ask2(int x, int l = 0, int r = n+1, int rt = 1) {
if (mn[rt] >= x) return inf;
if (l == r) return l;
int mid = (l + r) >> 1;
return mn[ls] < x ? ask2(x, l, mid, ls) : ask2(x, mid + 1, r, rs);
}
#undef ls
#undef rs
} T;
void del(int x, int v) {
int l = *prev(pos[v].lower_bound(x));
int r = *pos[v].upper_bound(x);
if (1 <= l) B.modify(l, x, inf);
if (r <= n) B.modify(x, r, inf);
if (1 <= l && r <= n) B.modify(l, r, v);
pos[v].erase(x), T.update(v);
}
void add(int x, int v) {
int l = *prev(pos[v].lower_bound(x));
int r = *pos[v].upper_bound(x);
if (1 <= l && r <= n) B.modify(l, r, inf);
if (1 <= l) B.modify(l, x, v);
if (r <= n) B.modify(x, r, v);
pos[v].emplace(x), T.update(v);
}
void _main() {
cin >> n >> q;
for (int i = 0; i <= n+1; i++) pos[i] = {0, n+1};
for (int i = 1; i <= n; i++) cin >> a[i], pos[a[i]].emplace(i);
T.build();
for (int i = 1; i <= n; i++) {
if (ls[a[i]]) B.modify(ls[a[i]], i, a[i]);
ls[a[i]] = i;
}
for (int x, v, l, r; q--; ) {
char op; cin >> op;
if (op == '?') {
cin >> l >> r;
cout << min({B.ask(l-1, r+1), T.ask1(r), T.ask2(l)}) << '\n';
} else {
cin >> x >> v;
del(x, a[x]), a[x] = v, add(x, v);
}
}
}
:::::
定义 区间
定理 2 极短 mex 区间的数目不超过
证明
取极短正 mex 区间
取固定的
对
问题 3 给定长为
对
设
条件二表明
对
在线段树上二分求出
考虑每次
注意特判区间 mex 为
定义 区间
问题 4 给定长为
使用问题 3 的算法求出所有极短 mex 区间,向两侧找到第一个改变 mex 的位置,得到对应的极长区间。
对
设
拍到
使用极长—极短 mex 区间构造的 mex 矩形是可重不漏的。为了构造不重不漏的 mex 矩形划分,可以在扫描线中输出
原理是将每个
特判
:::::info[代码]
int n, a[N], p[N];
vector<int> pos[N];
struct node {int x1, x2, y1, y2, v;};
vector<node> rec;
struct segtree {
#define ls (rt << 1)
#define rs (rt << 1 | 1)
int val[4*N];
void pushup(int rt) {val[rt] = min(val[ls], val[rs]);}
void update(int x, int c, int l = 0, int r = n+1, int rt = 1) {
if (l == r) return val[rt] = c, void();
int mid = (l + r) >> 1;
if (x <= mid) update(x, c, l, mid, ls);
else update(x, c, mid + 1, r, rs);
pushup(rt);
}
int ask(int tl, int tr, int l = 0, int r = n+1, int rt = 1) {
if (tl <= l && r <= tr) return val[rt];
int mid = (l + r) >> 1, res = n+1;
if (tl <= mid) chkmin(res, ask(tl, tr, l, mid, ls));
if (tr > mid) chkmin(res, ask(tl, tr, mid + 1, r, rs));
return res;
}
int mex(int c, int l = 0, int r = n+1, int rt = 1) {
if (l == r) return l;
int mid = (l + r) >> 1;
return val[ls] < c ? mex(c, l, mid, ls) : mex(c, mid + 1, r, rs);
}
} T;
void mexrect() {
for (int i = 0; i <= n+1; i++) pos[i].pb(0);
for (int i = 1; i <= n; i++) pos[a[i]].pb(i);
for (int i = 0; i <= n+1; i++) pos[i].pb(n+1);
for (int r = 1; r <= n; r++) {
int q = p[a[r]]; p[a[r]] = r;
T.update(a[r], r);
int l = a[r] ? T.ask(0, a[r] - 1) : r;
for (int y; l > q; l = p[y]) {
y = T.mex(l);
int R = *upper_bound(all(pos[y]), r) - 1;
rec.pb(node{max(q, p[y])+1, l, r, R, y});
}
}
// 特判 mex=0 的矩形
for (int k = 1; k < (int)pos[0].size(); k++) {
int L = pos[0][k-1] + 1, R = pos[0][k] - 1;
for (int i = L; i <= R; i++) rec.pb(node{i, i, i, R, 0});
}
}
:::::