Codeforces #267 Div2 E. Alex and Complicated Task

これは何とか自力で解けた。
http://codeforces.com/contest/467/problem/E

問題

N要素の整数列A[i]が与えられる。
ここから、４の倍数の要素数の(非連続でも良い)部分列B[i]を選び、B[4k]==B[4k+2]、B[4k+1]==B[4k+3]となるようにしたい。
条件を満たす要素数最大のB[i]を答えよ。

解法

まず事前にA[i]を２周見て、前後の同じ数値の位置prev[i],next[i]を求めておく。
また、Segment Treeで「次の同じ数値の位置」の最小値をO(logN)で求められるようにしておく。

後は左端から順にababまたはaaaaとなる最短の４要素を貪欲に抽出していく。
A[x]まで確定済みとして、A[x+1]以降で条件を満たす４要素を探すことを考える。

ababの２つ目のaの候補、すなわち「前の同じ数字の位置が確定済み要素より後にある(prev[i]＞x)」ようなA[j]に遭遇したら、A[P[i]+1]～A[j-1]の範囲で、SegTreeを使ってnext[k]＞iとなる最小のkを探していく。
この際以下の点に注意。

• next[k]＜iとなるkが見つかった場合、そのkは候補から外す(abbaになってしまう)
• ababでなくaaaaとなるケースをちゃんと考慮する。この場合(prev[prev[i]],prev[i],i,next[i])が抽出対象となる。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=10000000;
	V comp(V l,V r){ return min(l,r);};
	
	SegTree_1(){val.resize(NV*2); clear();};
	void clear() { int i; FOR(i,NV*2) val[i]=def;}
	
	V getval(int x,int y,int l,int r,int k) {
		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));
	}
	V getval(int x,int y) { return getval(x,y,0,NV,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]);
	}
};

int N;
int A[600000],p[600000],n[600000];
map<int,int> M;
vector<int> R;
SegTree_1<int,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	FOR(i,N) p[i]=M.count(A[i])?M[A[i]]:-1, M[A[i]]=i;
	M.clear();
	for(i=N-1;i>=0;i--) {
		n[i]=M.count(A[i])?M[A[i]]:N;
		M[A[i]]=i;
		st.update(i,n[i]);
	}
	int pre=-1;
	while(pre<N) {
		int mi=N;
		int V[4];
		for(i=pre+1;i<N;i++) {
			if(i>mi) break;
			if(p[i]<=pre) continue;
			if(p[p[i]]>pre && n[i]<mi){ //same
				V[0]=p[p[i]];
				V[1]=p[i];
				V[2]=i;
				mi=V[3]=n[i];
			}
			if(p[i]+2<=i) {
				while((j=st.getval(p[i]+1,i))<=i) {
					st.update(p[j],10000000); //disable;
				}
				if((j=st.getval(p[i]+1,i))<mi){
					V[0]=p[i];
					V[1]=p[j];
					V[2]=i;
					mi=V[3]=j;
				}
			}
		}
		if(mi<N) R.insert(R.end(),V,V+4);
		pre=mi;
		if(i>=N) break;
		
	}
	
	_P("%d\n",R.size());
	FOR(i,R.size()) _P("%d ",A[R[i]]);
	_P("\n");
}

まとめ

SegTreeの面白い使い方で良かった。