自动搬运

查看原文

来自洛谷，原作者为

	lsj2009 关关雎鸠，在河之洲

搬运于2025-08-24 22:53:29，当前版本为作者最后更新于2023-12-20 18:17:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

闲话

膜你赛刚做过类似的 trick，结果马上就用上了/jy

场上一下子就切了，没吃罚时，很爽！

Solution

结论

先说一个经典（？结论：

方便起见，先下一个定义：

我们称满足 $\text{mex}(l,r)=x$ 的区间为 $x\text{-mex}$ 区间。

对于一个 $x\text{-mex}$ 区间 $[l,r]$，如果不存在另一个 $x\text{-mex}$ 区间 $[l',r']\subset[l,r]$，则称 $[l,r]$ 为『极小的 mex 区间』。

• 则有结论：极小的 mex 区间只有 $\Theta(n)$ 个；具体的，一个上界是 $2n$。

• 证明：对于一个满足条件的『极小的 mex 区间』$[l,r]$ 显然满足 $a_l\ne a_r$，否则删任意一个不影响答案，不妨假设 $a_l>a_r$，则 $a_r$ 和 $a_l$ 的加入先后影响了 $\text{mex}(l,r)$ 的答案，则可以得到的是：$\text{mex}(l+1,r-1)=a_r$，由于当 $l$ 固定时 $\text{mex}$ 单调不降，且有多个满足他条件的 $r$ 只取最左边那个，所以对于任意的 $l$ 只有一个 $r$ 满足条件；同理，对于 $a_l<a_r$ 的情况，对于每个 $r$ 也至多只有一个 $l$ 满足条件，故最多只有 $2n$ 个『极小的 mex 区间』。

求『极小的 mex 区间』

然后我们考虑知道了这么一个性质只会要怎么做。

那么我们首先要把所有极小的 mex 区间给掏出来，这个好像说是有什么『阶梯状』的东西，和同学们讨论了一下，不是很懂（或者说感觉不是很好维护），这里讲一个比较脑瘫的求法。如果说你会比较优雅的求法，那么可以选择跳过。

假设我们已经求出 $\text{mex}=1\sim x-1$ 的答案，我们考虑如何推出 $\text{mex}=x$ 的答案。

那么一个比较显然的结论是：$\text{mex}=x$ 的一个答案区间必然是往 $\text{mex}=y(y<x)$ 的一个答案区间两边加上了 $y\sim x-1$ 然后得到。

然后我们就得到了一个求『极小的 mex 区间』的算法：

• 预处理出极小的 $0\text{-mex}$ 和 $1\text{-mex}$ 区间。
• 对于每一个极小的 $(x-1)\text{-mex}$ 区间分别求出其距离左端点最近的 $x-1$ 出现位置，和距离右端点最近的 $x-1$ 出现位置，形成两个新的区间，算一下两个区间的 $\text{mex}=x'$，然后丢到对应的存储 $x'\text{-mex}$ 区间的 vector 里。
• 对于存储 $x\text{-mex}$ 区间的 vector 求极小区间。

由于最终答案是 $2n$ 级别的，所以任何时刻的区间个数不会超过 $4n$ 级别，复杂度是 $\Theta(n\log{n})$。

对于实现细节：

• 求在某个点左/右侧最近的 $=x$ 的点：开 $n$ 个 vector，分别存储每个数的出现位置，vector 上二分即可。

• 在线求区间 mex：这个也就是 P4137，主席树即可，不再赘述。

计算答案

我们考虑对于每个『极小的 $x\text{-mex}$ 区间』$S$ 求出其对应的『极大的 $x\text{-mex}$ 区间』$S'$。

则对于任意 $k\in[|S|,|S'|]$ 的集合都可以拥有 $x$ 这个数，我们考虑把区间 $[|S|,|S'|]$ 推平成 $1$。

然后对于最终为 $0$ 的点显然 mex 不大于 $x$。

则我们倒着枚举 $x$，每次将其为 $0$ 的点在答案序列上位置修改成 $x$，最终即为答案。

至于区间推平，ODT 即可。

需要注意的是，这里 ODT 复杂度不依赖于随机，而依赖于均摊。

具体的，每次未被推平成 $0$ 的节点构成了若干个区间，区间总数至多为 $|S_x|+1$ 个（$S_x$ 表示『极小的 $x\text{-mex}$ 区间』个数），由于 $\sum |S_x|\le 2n$，所以总共不会被推平超过 $3n$ 次。

最终复杂度 $\Theta(n\log{n})$。

常数看起来很大，但是实际上跑得很快，不是很懂。

Code

#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
bool M1;
void file_IO() {
//	freopen("mushroom.in","r",stdin);
//	freopen("mushroom.out","w",stdout);
}
const int N=1e5+5;
int a[N],n,q;
vector<int> vec[N];
vector<PII> g[N];
inline int pre(const vector<int> &vec,const int& x) {
	auto p=upper_bound(vec.begin(),vec.end(),x);
	if(p!=vec.begin())
		return *(--p);
	return -1;
}
inline int nxt(const vector<int> &vec,const int& x) {
	auto p=lower_bound(vec.begin(),vec.end(),x);
	if(p!=vec.end())
		return *p;
	return -1;
}
struct PSGT {
	struct node {
		int lson,rson,val;
	}; node tree[N*20];
	int p;
	inline int new_node(const int& k) {
		tree[++p]=tree[k];
		return p;
	}
	inline void push_up(const int& k) {
		tree[k].val=min(tree[tree[k].lson].val,tree[tree[k].rson].val);
	}
	void update(int &k,const int& l,const int& r,const int& qx,const int& val) {
		k=new_node(k);
		if(l==r) {
			tree[k].val=val;
			return;
		}
		int mid=(l+r)>>1;
		if(qx<=mid)
			update(tree[k].lson,l,mid,qx,val);
		if(qx>=mid+1)
			update(tree[k].rson,mid+1,r,qx,val);
		push_up(k);
	}
	int query(const int& k,const int& l,const int& r,const int& ql,const int& qr) {
		if(l==r)
			return l;
		int mid=(l+r)>>1,val=tree[tree[k].lson].val;
		if(val<ql)
			return query(tree[k].lson,l,mid,ql,qr);
		return query(tree[k].rson,mid+1,r,ql,qr);
	}
	int root[N],cnt;
	inline void ins(const int& x) {
		++cnt;
		root[cnt]=root[cnt-1];
		update(root[cnt],0,n,x,cnt);
	}
}; PSGT T2;
inline int mex(const int& l,const int& r) {
	return T2.query(T2.root[r],0,n,l,r);
}
struct ODT {
	struct node {
		int l,r;
		mutable int val;
		node() {
			l=r=val=0;
		}
		node(int _l,int _r,int _val) {
			l=_l; r=_r; val=_val;
		}
		bool operator < (const node &tmp) const {
			return l<tmp.l;
		}
	}; set<node> s;
	ODT() {
		s.clear();
		s.insert(node{1,n,0});
	}
	auto split(int pos) {
		auto p=s.lower_bound(node(pos,0,0));
		if(p!=s.end()&&(*p).l==pos)
			return p;
		--p;
		if((*p).r<pos)
			return s.end();
		int l=(*p).l,r=(*p).r,val=(*p).val;
		s.erase(p);
		s.insert(node(l,pos-1,val));
		auto t=s.insert(node(pos,r,val));
		return t.first;
	}
	void assign(int l,int r,int val) {
		auto _r=split(r+1),_l=split(l);
		s.erase(_l,_r);
		s.insert(node(l,r,val));
	}
	auto ins(int p,int val) {
		auto t=s.insert(node(p,p,val));
		return t.first;
	}
}; ODT T,T1;
int ans[N];
inline void solve() {
	scanf("%d",&n);
	rep(i,1,n) {
		scanf("%d",&a[i]);
		vec[a[i]].push_back(i);
		T2.ins(a[i]);
	}
	rep(i,1,n) {
		if(a[i])
			g[0].push_back({i,i});
		else
			g[1].push_back({i,i});
	}
	rep(i,1,n) {
		for(auto x:g[i-1]) {
			int l=x.first,r=x.second;
			int pl=pre(vec[i-1],l),pr=nxt(vec[i-1],r);
			if(pl!=-1)
				g[mex(pl,r)].push_back({pl,r});
			if(pr!=-1)
				g[mex(l,pr)].push_back({l,pr});
		}
		sort(g[i].begin(),g[i].end(),[](const PII &a,const PII &b) {
			return a.first>b.first||(a.first==b.first&&a.second<b.second);
		});
		vector<PII> tmp;	
		int last=INF;
		for(auto x:g[i]) {
			if(last>x.second)
				tmp.push_back(x);
			chkmin(last,x.second);
		}
		swap(g[i],tmp);
	}
	T1=ODT();
	per(i,n+1,0) {
		T=ODT();
		for(auto x:g[i]) {
			int l=x.first,r=x.second;
			int pl=pre(vec[i],l),pr=nxt(vec[i],r);
			if(pl==-1)
				pl=1;
			else
				++pl;
			if(pr==-1)
				pr=n;
			else
				--pr;
			T.assign(r-l+1,pr-pl+1,1);
		}
		for(auto x:T.s) {
			int l=x.l,r=x.r,val=x.val;
			if(!val)
				T1.assign(l,r,i);
		}
	}
	for(auto x:T1.s) {
		int l=x.l,r=x.r,val=x.val;
		rep(i,l,r)
			printf("%d ",val);
	}
}
bool M2;
signed main() {
	file_IO();
	int testcase=1;
	//scanf("%d",&testcase);
	while(testcase--)
		solve();
//	cerr<<"used time = "<<1000.0*clock()/CLOCKS_PER_SEC<<"ms\n";
//	cerr<<"used memory = "<<(&M1-&M2)/1024/1024<<"MB\n";
	return 0;
}