Codeforces #204 Div1 D. Jeff and Removing Periods

過去のCF Div1D埋め、早く書かないと忘れそう。
http://codeforces.com/contest/351/problem/D

問題

ある整数列Aに対し、１回の処理で以下の内容を順に行える。

• A[v]=A[v+t]=A[v+2*t]=...=A[A+k*t]であるようなv,t,kを選択し、それらの要素をすべて取り除く。
• 残された要素を任意に並び替える。

整数列Aの美しさとは、上記処理を繰り返してAを消しきるまでの最小処理回数である。

ここで、N要素の整数列Bが与えられる。
Q個のクエリL[i],R[i]が与えられるので、部分列B[L[i]..R[i]]に対する美しさを求めよ。

解法

部分列の両端を１つずつ伸ばしたり縮めたりする処理を行っていく。
そのため、クエリを先に並べ替えよう。
伸びちじみの回数を減らすため、平方分割による並べ替えテクが利用できる。
単純にLやRの値でソートするのではなく、(L/√N,R)の値でソートする。
こうすると、右端を最初から最後まで伸ばす処理は√N回で済むし、１回あたりの左端の伸びちじみ量はL/√Nですむ。
結果、部分列の両端を伸びちじみする回数はO(N^1.5)に抑えられる。

次に、処理の最小回数を考える。
初回の処理で最初Aの要素を一部消した後は、Aを要素順にソートすればあとはAのuniqueな要素数分処理を行えば数字を消しきることができる。
よって、初回の処理で１つの数字を消しきれれば、処理回数はAのuniqueな要素数の数と一致するし、どうやっても消しきれないなら初回分１回多く処理が必要となる。

そこで前処理として、B[i]に対し、手前と奥方向に同じ数字が等間隔でどこまで続くかを覚えておく。
部分列の両端を伸びちじみさせる過程で、ある数字が部分列内でずっと等間隔であるようなものの数を増減させておき、そのようなものが１個以上あれば、「初回の処理で１つの数字を消しきれれば」が可能となる。

int M;
int B[100001];
int pre[100001], pre2[100001];
int post[100001], post2[100001];
int la[2][100001];

int Q;
int L[100001],R[100001];
pair<pair<int,int>,pair<int,int> > P[100001];

int tnum,ok;
int num[100001],res[100001];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>M;
	FOR(i,100001) la[0][i]=0, la[1][i]=M+1;
	for(i=1;i<=M;i++) {
		cin>>B[i];
		pre[i]=x=la[0][B[i]];
		la[0][B[i]]=i;
		if(i-x==x-pre[x]) pre2[i]=pre2[x];
		else pre2[i]=pre[x]+1;
	}
	post[M+1]=post2[M+1]=M+1;
	for(i=M;i>=1;i--) {
		post[i]=x=la[1][B[i]];
		la[1][B[i]]=i;
		if(i-x==x-post[x]) post2[i]=post2[x];
		else post2[i]=post[x]-1;
	}
	
	cin>>Q;
	FOR(i,Q) {
		cin>>L[i]>>R[i];
		P[i]=make_pair(make_pair(L[i]/300,R[i]),make_pair(L[i],i));
	}
	sort(P,P+Q);
	
	l=1,r=1;
	tnum=ok=1;
	num[B[1]]=1;
	FOR(i,Q) {
		j=P[i].second.second;
		while(L[j]<l) {
			l--;
			if(num[B[l]]++==0) tnum++, ok++;
			else if(post2[post[l]]>=r && post2[l]<r) ok--;
		}
		while(r<R[j]) {
			r++;
			if(num[B[r]]++==0) tnum++, ok++;
			else if(pre2[pre[r]]<=l && pre2[r]>l) ok--;
		}
		while(l<L[j]) {
			if(--num[B[l]]==0) tnum--, ok--;
			else if(post2[l]<r && post2[post[l]]>=r) ok++;
			l++;
		}
		while(R[j]<r) {
			if(--num[B[r]]==0) tnum--, ok--;
			else if(pre2[r]>l && pre2[pre[r]]<=l) ok++;
			r--;
		}
		res[j]=tnum+(ok==0);
	}
	
	FOR(i,Q) cout<<res[i]<<endl;
}

まとめ

伸びちじみさせつつ等間隔な数字の数を求めるテクも難しいけど、この(L/√N,R)でソートして伸びちじみ回数をO(N^1.5)で抑えるテクも難しい。
でもこのテクはしばしば使えそうだな。