题解【CF1436E Complicated Computations】

CF1436E Complicated Computations
解题报告。
不一定更好的阅读体验。

对于一个数 \(x\)，考虑什么条件 \(x\) 可以作为答案。

首先要满足 \(\forall y\in [1,x)\)，\(y\) 都不能作为答案，因为最终我们是取的 mex。

其次，原序列任何一个连续子序列的 mex 都不可能为 \(x\)。

第一个条件我们只需要顺着枚举 \(x\) 即可，考虑如何解决第二个条件限制。

我们把 \(x\) 在原序列出现的位置都提出来，这样会把原序列分割成若干不包含 \(x\) 的极长子区间。

任何一个包含 \(x\) 的子区间的 mex 都不可能为 \(x\)，所以我们只需要检查分割出来的所有子区间中是否存在一个区间的 mex 是 \(x\)，只要有就不合法。

对于每一个 \(x\) 这些子区间显然是可以暴力处理的出来的，因为区间总数是不超过 \(O(n)\) 个的。

于是现在就变成区间求 mex 的问题，可以考虑可持久化权值线段树，

具体的，对于一个询问区间 \([l,r]\)，我们提出以 \([1,r]\) 这个序列建出的的权值线段树，维护每一个数最后出现的位置，若一个数最后出现的位置小于 \(l\)，说明这个数可能作为 mex，而真正的 mex 是这些数的 \(\min\)。

这就典了啊，线段树上二分乱杀即可。有限走左子树，然后走右子树。

时间复杂度 \(\Theta(n\log n)\)，比莫队套值域分块快多了。

代码（自认为写得比较好看）：

const int MAXN(1e5+10);

int n,m,a[MAXN];
bool flag[MAXN];

vector<int>G[MAXN];
struct node{int l,r,v;};
node q[MAXN<<1];


inline void newquery(int l,int r,int v){if(l>r)return;q[++m].l=l;q[m].r=r,q[m].v=v;return;}
inline bool cmp(node x,node y){return x.r<y.r;}

int rt[MAXN];

struct Segment_Tree
{
	struct T{int ls,rs,val;};
	T tree[MAXN*30];
	int tot;

	inline int lc(int u){return tree[u].ls;}
	inline int rc(int u){return tree[u].rs;}

	inline void push_up(int u)
	{
		tree[u].val=Min(tree[tree[u].ls].val,tree[tree[u].rs].val);
		return;
	}

	inline void update(int&u,int pre,int l,int r,int p,int k)
	{
		u=++tot;
		tree[u]=tree[pre];
		if(l==r)
		{
			tree[u].val=k;
			return;
		}
		int mid=(l+r)>>1;
		if(p<=mid) update(tree[u].ls,tree[pre].ls,l,mid,p,k);
		else update(tree[u].rs,tree[pre].rs,mid+1,r,p,k);
		push_up(u);
		return;
	}

	inline int query(int u,int l,int r,int L)
	{
		if(l==r) return l;
		int mid=(l+r)>>1;
		if(tree[lc(u)].val<L) return query(lc(u),l,mid,L);
		else return query(rc(u),mid+1,r,L);
	}
};
Segment_Tree seg;

int main()
{
	n=read();
	rep(i,1,n) a[i]=read(),G[a[i]].push_back(i);
	rep(i,1,n)
	{
		rep(j,0,(int)G[i].size()-1)
		{
			if(j==0) newquery(1,G[i][j]-1,i);
			else newquery(G[i][j-1]+1,G[i][j]-1,i);
		}
		if(G[i].size()) newquery(G[i][G[i].size()-1]+1,n,i);
	}
	rep(i,1,n)
		seg.update(rt[i],rt[i-1],1,n+1,a[i],i);
	rt[n+1]=rt[n];
	rep(i,1,m)
	{
		int l=q[i].l,r=q[i].r,v=q[i].v;
		if(seg.query(rt[r],1,n+1,l)==v) flag[v]=true; 
	}
	rep(i,1,n+2) if(seg.query(rt[n+1],1,n+1,1)==i) flag[i]=true;
	rep(i,1,n+2) if(!flag[i])
	{
		printf("%d\n",i);
		return 0;
	}
    return 0;
}
/*
Date : 2022/9/27
Author : UperFicial
Start coding at : 7:05
finish debugging at : 9:34
*/