1935B - Informatics in MAC

这道题目考察了前缀和的思想以及对数学思维的理解，首先对于任意一组数组

0 1 7 1 0 1 0 3

考虑一下他们之间的MEX怎么分割，假设有两个数组{1，x}，{x+1，n}要使得他们之间的MEX一样，则他们每个数组中都含有1~MEX-1个数（一定）那么把两个数组合并呢？

两个数组合并之后MEX不变，则往下递推，假设分成k组，那么k-1组也一定满足该条件，换句话说，只要有k组能成立，那么把一整个数组分成2组也一定成立，那么就从1~n一个个枚举，判断1~i和i+1~n之间是否存在相同的MEX，如果存在，那么就一定成立，否则输出-1

#include <bits/stdc++.h>
using namespace std;
const int N =1e5+5;
int a[N];
int vis1[N],vis2[N],st[N],st2[N];
int n;

void solve(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	memset(vis1,0,sizeof(vis1));
	memset(vis2,0,sizeof(vis2));
	memset(st,0,sizeof(st));
	memset(st2,0,sizeof(st2));
	
	int min1=0;
	for(int i=1;i<=n;i++){
		if(!vis1[a[i]]){
			vis1[a[i]]=1;
		}
		while(vis1[min1]){
			min1++;
		}
		st[i]=min1;
	}
	
	int min2=0;
	for(int i=n;i>=1;i--){
		if(!vis2[a[i]]){
			vis2[a[i]]=1;
		}
		while(vis2[min2]){
			min2++;
		}
		st2[i]=min2;
	}
	bool flag=false;
	int pos;
	for(int i=1;i<n;i++){
		if(st[i]==st2[i+1]){
			flag=true;
			pos=i;
			break;
		}
	}
	
	if(!flag)cout<<-1<<"\n";
	else {
		cout<<2<<"\n";
		cout<<1<<" "<<pos<<"\n";
		cout<<pos+1<<" "<<n<<"\n";
	}
	
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t;cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}