[题目链接](https://qoj.ac/contest/1894/problem/9986) 超妙的一道题 对于一次区间加 mex 操作，考虑如何求出 mex 从 0,1,2,... 开始判断每个数是否都存在，每次只需要判断区间最小值是否等于当前的数，找完之后可以暂时标记成无穷大 第一个找不到的数即为 mex 然后恢复标记，再把区间加上 mex 这看起来很暴力，但实际上均摊复杂度并不大 因为区间内所有<mex 的数在操作后都会至少变成原来的两倍，而 mex 最大值不会超过 n，也就是说每个数最多影响 mex 并被打上标记最多 O(log n) 次 这时的时间复杂度时 O(nlog²n) 但还有区间赋值操作 我们同样可以用类似的方法，只不过每次把某个数标记成无穷大时需要把这整个区间标记成无穷大 对于某个区间，在线段树上被分为了 log 段，但在打标记的复杂度还是 O(log n) 的 但数字变小后似乎还能继续+mex 看似时间复杂度变大了 但从整个过程来考虑，如果一段区间的值是相等的，我们可以假装它是连在一起一个数，并且我们钦定在未来的操作中它们都是一起变化 但如果某次操作使得它们会变成不同的数，我们可以在开始就假装它们是多段不同的区间（多个数） 那么整个过程中出现不同数的数量为 O(n+m) 依旧可以保证 +mex 后的复杂度 总复杂度为 O((n+m)log²n) 代码会比较长，但实际上只是在线段树区间加、区间赋值的模板上增加一些操作 ```cpp #include <bits/stdc++.h> #define int long long #define INF 1000000000000ll #define lp p<<1 #define rp p<<1|1 using namespace std; const int N=5e5+10; int n, q, a[N]; struct seg { int s[N*4], mn[N*4], t1[N*4], t2[N*4], flag[N*4]; void pushup(int p) { s[p]=s[lp]+s[rp]; mn[p]=min(mn[lp], mn[rp]); } void build(int p, int l, int r) { t1[p]=-1;//assign lazy tag t2[p]=0;//add lazy tag if (l==r) { s[p]=mn[p]=a[l]; return; } int mid=l+r>>1; build(lp, l, mid); build(rp, mid+1, r); pushup(p); } void pushdown(int p, int l, int r) { int mid=l+r>>1; if (t1[p]!=-1) { Assign(lp, l, mid, t1[p]); Assign(rp, mid+1, r, t1[p]); t1[p]=-1; } if (t2[p]!=0) { Add(lp, l, mid, t2[p]); Add(rp, mid+1, r, t2[p]); t2[p]=0; } } void Assign(int p, int l, int r, int k) { s[p]=k*(r-l+1); mn[p]=t1[p]=k; t2[p]=0; } void assign(int p, int l, int r, int L, int R, int k) { if (L<=l && r<=R) { Assign(p, l, r, k); return; } pushdown(p, l, r); int mid=l+r>>1; if (L<=mid) assign(lp, l, mid, L, R, k); if (R>mid) assign(rp, mid+1, r, L, R, k); pushup(p); } void Add(int p, int l, int r, int k) { mn[p]+=k; s[p]+=(r-l+1)*k; t2[p]+=k; } void add(int p, int l, int r, int L, int R, int k) { if (L<=l && r<=R) { Add(p, l, r, k); return; } pushdown(p, l, r); int mid=l+r>>1; if (L<=mid) add(lp, l, mid, L, R, k); if (R>mid) add(rp, mid+1, r, L, R, k); pushup(p); } void change(int p, int l, int r, int L, int R, int now) { if (mn[p]>now) return; if (L<=l && r<=R) { if (s[p]==now*(r-l+1)) { Add(p, l, r, INF); flag[p]=1; return; } } pushdown(p, l, r); int mid=l+r>>1; if (L<=mid) change(lp, l, mid, L, R, now); if (R>mid) change(rp, mid+1, r, L, R, now); pushup(p); flag[p]=flag[lp]|flag[rp]; } void restore(int p, int l, int r, int L, int R) { if (!flag[p]) return; if (L<=l && r<=R) { if (s[p]==mn[p]*(r-l+1) && mn[p]>=INF) { Add(p, l, r, -INF); flag[p]=0; return; } } pushdown(p, l, r); int mid=l+r>>1; if (L<=mid) restore(lp, l, mid, L, R); if (R>mid) restore(rp, mid+1, r, L, R); pushup(p); flag[p]=flag[lp]|flag[rp]; } int ask(int p, int l, int r, int L, int R) { if (L<=l && r<=R) return s[p]; pushdown(p, l, r); int mid=l+r>>1, res=0; if (L<=mid) res=ask(lp, l, mid, L, R); if (R>mid) res+=ask(rp, mid+1, r, L, R); return res; } int ask2(int p, int l, int r, int L, int R) { if (L<=l && r<=R) return mn[p]; pushdown(p, l, r); int mid=l+r>>1, res=INF; if (L<=mid) res=ask2(lp, l, mid, L, R); if (R>mid) res=min(res, ask2(rp, mid+1, r, L, R)); return res; } } S; signed main() { scanf("%lld%lld", &n, &q); for (int i=1; i<=n; i++) scanf("%lld", &a[i]); S.build(1, 1, n); while (q--) { int op, l, r, x; scanf("%lld%lld%lld", &op, &l, &r); if (op==1) { scanf("%lld", &x); S.assign(1, 1, n, l, r, x); } else if (op==2) { int lst=-1; while (1) { int now=S.ask2(1, 1, n, l, r); if (now==lst+1) { S.change(1, 1, n, l, r, now); lst=now; } else { S.restore(1, 1, n, l, r); S.add(1, 1, n, l, r, lst+1); break; } } } else printf("%lld\n", S.ask(1, 1, n, l, r)); } return 0; } ``` Loading... [题目链接](https://qoj.ac/contest/1894/problem/9986) 超妙的一道题 对于一次区间加 mex 操作，考虑如何求出 mex 从 0,1,2,... 开始判断每个数是否都存在，每次只需要判断区间最小值是否等于当前的数，找完之后可以暂时标记成无穷大 第一个找不到的数即为 mex 然后恢复标记，再把区间加上 mex 这看起来很暴力，但实际上均摊复杂度并不大 因为区间内所有<mex 的数在操作后都会至少变成原来的两倍，而 mex 最大值不会超过 n，也就是说每个数最多影响 mex 并被打上标记最多 O(log n) 次 这时的时间复杂度时 O(nlog²n) 但还有区间赋值操作 我们同样可以用类似的方法，只不过每次把某个数标记成无穷大时需要把这整个区间标记成无穷大 对于某个区间，在线段树上被分为了 log 段，但在打标记的复杂度还是 O(log n) 的 但数字变小后似乎还能继续+mex 看似时间复杂度变大了 但从整个过程来考虑，如果一段区间的值是相等的，我们可以假装它是连在一起一个数，并且我们钦定在未来的操作中它们都是一起变化 但如果某次操作使得它们会变成不同的数，我们可以在开始就假装它们是多段不同的区间（多个数） 那么整个过程中出现不同数的数量为 O(n+m) 依旧可以保证 +mex 后的复杂度 总复杂度为 O((n+m)log²n) 代码会比较长，但实际上只是在线段树区间加、区间赋值的模板上增加一些操作 ```cpp #include <bits/stdc++.h> #define int long long #define INF 1000000000000ll #define lp p<<1 #define rp p<<1|1 using namespace std; const int N=5e5+10; int n, q, a[N]; struct seg { int s[N*4], mn[N*4], t1[N*4], t2[N*4], flag[N*4]; void pushup(int p) { s[p]=s[lp]+s[rp]; mn[p]=min(mn[lp], mn[rp]); } void build(int p, int l, int r) { t1[p]=-1;//assign lazy tag t2[p]=0;//add lazy tag if (l==r) { s[p]=mn[p]=a[l]; return; } int mid=l+r>>1; build(lp, l, mid); build(rp, mid+1, r); pushup(p); } void pushdown(int p, int l, int r) { int mid=l+r>>1; if (t1[p]!=-1) { Assign(lp, l, mid, t1[p]); Assign(rp, mid+1, r, t1[p]); t1[p]=-1; } if (t2[p]!=0) { Add(lp, l, mid, t2[p]); Add(rp, mid+1, r, t2[p]); t2[p]=0; } } void Assign(int p, int l, int r, int k) { s[p]=k*(r-l+1); mn[p]=t1[p]=k; t2[p]=0; } void assign(int p, int l, int r, int L, int R, int k) { if (L<=l && r<=R) { Assign(p, l, r, k); return; } pushdown(p, l, r); int mid=l+r>>1; if (L<=mid) assign(lp, l, mid, L, R, k); if (R>mid) assign(rp, mid+1, r, L, R, k); pushup(p); } void Add(int p, int l, int r, int k) { mn[p]+=k; s[p]+=(r-l+1)*k; t2[p]+=k; } void add(int p, int l, int r, int L, int R, int k) { if (L<=l && r<=R) { Add(p, l, r, k); return; } pushdown(p, l, r); int mid=l+r>>1; if (L<=mid) add(lp, l, mid, L, R, k); if (R>mid) add(rp, mid+1, r, L, R, k); pushup(p); } void change(int p, int l, int r, int L, int R, int now) { if (mn[p]>now) return; if (L<=l && r<=R) { if (s[p]==now*(r-l+1)) { Add(p, l, r, INF); flag[p]=1; return; } } pushdown(p, l, r); int mid=l+r>>1; if (L<=mid) change(lp, l, mid, L, R, now); if (R>mid) change(rp, mid+1, r, L, R, now); pushup(p); flag[p]=flag[lp]|flag[rp]; } void restore(int p, int l, int r, int L, int R) { if (!flag[p]) return; if (L<=l && r<=R) { if (s[p]==mn[p]*(r-l+1) && mn[p]>=INF) { Add(p, l, r, -INF); flag[p]=0; return; } } pushdown(p, l, r); int mid=l+r>>1; if (L<=mid) restore(lp, l, mid, L, R); if (R>mid) restore(rp, mid+1, r, L, R); pushup(p); flag[p]=flag[lp]|flag[rp]; } int ask(int p, int l, int r, int L, int R) { if (L<=l && r<=R) return s[p]; pushdown(p, l, r); int mid=l+r>>1, res=0; if (L<=mid) res=ask(lp, l, mid, L, R); if (R>mid) res+=ask(rp, mid+1, r, L, R); return res; } int ask2(int p, int l, int r, int L, int R) { if (L<=l && r<=R) return mn[p]; pushdown(p, l, r); int mid=l+r>>1, res=INF; if (L<=mid) res=ask2(lp, l, mid, L, R); if (R>mid) res=min(res, ask2(rp, mid+1, r, L, R)); return res; } } S; signed main() { scanf("%lld%lld", &n, &q); for (int i=1; i<=n; i++) scanf("%lld", &a[i]); S.build(1, 1, n); while (q--) { int op, l, r, x; scanf("%lld%lld%lld", &op, &l, &r); if (op==1) { scanf("%lld", &x); S.assign(1, 1, n, l, r, x); } else if (op==2) { int lst=-1; while (1) { int now=S.ask2(1, 1, n, l, r); if (now==lst+1) { S.change(1, 1, n, l, r, now); lst=now; } else { S.restore(1, 1, n, l, r); S.add(1, 1, n, l, r, lst+1); break; } } } else printf("%lld\n", S.ask(1, 1, n, l, r)); } return 0; } ``` 最后修改：2026 年 01 月 05 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏