Codeforces ECR #065 : E. Range Deleting

Codeforcesの記事書くのどんどん遅れていく…。
https://codeforces.com/contest/1167/problem/E

問題

1～Xのいずれかの整数値からなる数列Aが与えられる。
区間[L,R]のうち、Aから値が[L,R]の範囲に収まるものを除くと単調増加になるものは何通りか。

解法

各値について、登場する区間を求めておく。
値pについて、以下を求めておく。

• p以下の値をすべてAに残す場合、それらのうちもっとも右の位置。ただしその際に単調増加を保てない場合、数列の終端とする。
• p以上の値をすべてAに残す場合、それらのうちもっとも左の位置。ただしその際に単調増加を保てない場合、数列の先端とする。

Lを総当たりし、その際条件を満たすRを求めていこう。
(L-1)の上の値より、(R+1)の下の値が大きければ、(L-1)以下の数列の後に(R+1)以上の数列が現れるので、[L,R]は条件を満たす。
あとはRを二分探索していけばよい。

int N,X;
int A[1010101];
int L[1010101],R[1010101];
int LL[1010101],RR[1010101];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&X);
	FOR(i,X+1) {
		L[i]=N;
		R[i]=-1;
	}
	
	FOR(i,N) {
		scanf("%d",&x);
		R[x]=i;
		L[x]=min(L[x],i);
	}
	RR[0]=-1;
	for(x=1;x<=X;x++) {
		if(L[x]<RR[x-1]) RR[x]=N+1;
		else RR[x]=max(R[x],RR[x-1]);
	}
	LL[X+1]=N;
	for(x=X;x>=1;x--) {
		if(R[x]>LL[x+1]) LL[x]=-2;
		else LL[x]=min(L[x],LL[x+1]);
	}
	ll ret=0;
	int rr=1;
	for(x=1;x<=X;x++) {
		if(RR[x-1]>=N) break;
		
		if(RR[x-1]<=LL[x+1]) {
			ret+=(X+1-x);
			continue;
		}
		
		rr=x;
		for(i=20;i>=0;i--) if(rr+(1<<i)<=X && RR[x-1]>LL[rr+(1<<i)]) rr+=1<<i;
		ret+=(X-rr+1);
	}
	cout<<ret<<endl;
	
}

まとめ

なんか本番えらく苦戦してるな。