Codeforces #678 Div2 E. Complicated Computations

Fが解けたのにEが解けていない…。
http://codeforces.com/contest/1436/problem/E

問題

整数列Eが与えられる。
連続部分列におけるmex値を、全連続部分列に対し取った整数集合を考える。
この整数集合に対するmex値を求めよ。

解法

Aの全要素が1なら、どの連続部分列のmex値も2になるので、それらのmex値は1。
逆にAに1が1個もなければ、連続部分列のmex値も1になるので、それらのmex値は2。

以降それ以外のケースを考える。
Aを端から順に走査していくとき、SegTreeで各値が登場した最後のindexを更新していく。

今A[i]を走査するとき、同じA[j]=A[i]となるi未満の最大のjに対し、A[(j+1)....(i-1)]の間にA[i]未満の全値が登場するなら、mex値A[i]+1となる部分列が取れる。
これは上記SegTreeでRMQを処理することで確認できる。

あとはこれらの登場済みmex値の集合を用いて、最終的なmex値を求めよう。

int N;
int A[101010];
vector<int> cand[101010];
int is[101010];
int pre[101010];
template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=1<<30;
	V comp(V l,V r){ return min(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,-2);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<int,1<<17> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N+2) cand[i].push_back(-1);
	FOR(i,N) {
		cin>>A[i];
		pre[i]=cand[A[i]].back();
		cand[A[i]].push_back(i);
		
		if(A[i]==1) {
			is[1]=1;
		}
		else if(st.getval(1,A[i])>pre[i]) {
			is[A[i]]=1;
		}
		st.update(A[i],i);
	}
	
	if(count(A,A+N,1)==N) return _P("1\n");
	if(count(A,A+N,1)==0) return _P("2\n");
	
	
	for(i=2;i<=N+1;i++) if(st.getval(1,i)>cand[i].back()) is[i]=1;
	
	for(i=1;i<=N+2;i++) if(is[i]==0) break;
	cout<<i<<endl;
	
	
}

まとめ

本番もみなEの方を解いてるんだよな…。