正题

题目链接:http://codeforces.com/contest/1628/problem/A

---

题目大意

给出一个长度为\(n\)的序列\(a\)和一个空序列\(b\)，你每次可以选择\(a\)的一个前缀，将它的\(mex\)加入序列\(b\)的末尾，然后将\(a\)的这个前缀删除。

求\(b\)的最大字典序。

\(1\leq \sum n\leq 2\times 10^5,0\leq a_i\leq n\)

---

解题思路

显然地我们每次肯定要选\(mex\)最大的一个前缀，为了最大化我们后面的值，那么我们显然是选的前缀越短越好。

而考虑如何快速求到这个前缀，我们可以考虑从小到大枚举这个\(mex\)的值，假设现在枚举到\(x\)，那么证明我们得到的前缀\(1\sim r\)之中已经有\(0\sim x-2\)了，我们就先看这个前缀中是否有\(x-1\)，如果有就枚举下一个数，不然我们就让\(r\)跳到第一个\(x\)处。

显然这样一次的复杂度是\(O(mex\log n)\)的，但是因为删除的数字个数和\(mex\)同级，而一个数字最多被删除一次，这样时间复杂度就是\(O(n\log n)\)了。

写个\(vector\)上二分就好了。

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=2e5+10;
int T,n;vector<int> v[N],mex;
int lb(int x,int L){
	int l=0,r=v[x].size()-1;
	while(l<=r){
		int mid=(l+r)>>1;
		if(v[x][mid]<=L)l=mid+1;
		else r=mid-1;
	}
	return (l>=v[x].size())?(n+1):v[x][l];
}
int main()
{
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);mex.clear();
		for(int i=0;i<=n;i++)v[i].clear();
		for(int i=1,x;i<=n;i++){
			scanf("%d",&x);
			v[x].push_back(i);
		}
		int l=0;
		while(l<n){
			int r=l+1;
			for(int i=0;i<=n;i++){
				int p=lb(i,l);
				if(p>n){
					mex.push_back(i);
					break;
				}
				r=max(p,r);
			}
			l=r;
		}
		printf("%d\n",mex.size());
		for(int i=0;i<mex.size();i++)
			printf("%d ",mex[i]);
		putchar('\n');
	}
}