Codeforces #345 Div1. D. Zip-line

こちらもDにしては簡単。
http://codeforces.com/contest/650/problem/D

問題

N要素の数列Hが与えられる。
これに対し、M個のクエリに答えよ。

各クエリはA[i],B[i]の2値からなる。
H[A[i]]=B[i]とHを更新した際、LISの長さを答えよ。
(Hの値はクエリ毎に戻る)

解法

もともと更新前のH[A[i]]がHのLISに含まれる場合、H[A[i]]を書き換えることでLISが1つ短くなるかもしれない。
逆にH[A[i]]を書き換えることでLISが1つ長くなるかもしれない。

まず前者の方を片付けよう。
一般的なLISの求め方を用い、H[i]が末尾となる単調増加列の最長の長さL[i]を求めよう。
次に、各要素がLISに含まれうるかどうかは、Hを後ろから見ていくことで判断できる。
L[i]がLISの長さと一致するか、もしくは「H[i]以降にH[j]＞H[i]かつL[j]=L[i]+1かつH[j]がLISに含まれうる」を判定することで判断できる。
また、LISに含まれうる要素のうち、L[i]の値が唯一である要素がある場合、その要素がなくなるとLISが1つ短くなる。

ここまで行うと、各クエリについてH[A[i]]がなくなった場合、LISが1短くなるかどうかを判断できる。
次に、H[A[i]]=B[i]と更新した場合、LISがどうなるか考えよう。
まずクエリをA[i]ごとにバケツソートの要領で並べ替える。

あとはLISと同様にH[i]にL[i]を求める処理を行い、H[A[i]]を処理する際、H[A[i]]が代わりにB[i]と更新された場合、B[i]が単調増加列の何番目に来るか求めるとよい。
同様にHを逆順にたどり、B[i]が単調減少列の何番目に来るかを順次求め、H[A[i]]以前の単調増加列とH[N-1]～H[A[i]](逆順)までの単調減少列の長さを求めると、B[i]を含むLIS長が求められる。

int N,M;
int H[404040];
int L[404040];
vector<pair<int,int>> E[404040];
int R[404040];
int ma[404040];
int step[404040];
int ok[404040];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	vector<int> LIS(N+1,1<<30);
	int MAL=0;
	LIS[0]=0;
	FOR(i,N) {
		cin>>H[i];
		L[i] = lower_bound(LIS.begin(),LIS.end(),H[i]) - LIS.begin();
		LIS[L[i]] = H[i];
		MAL=max(MAL,L[i]);
	}
	for(i=N-1;i>=0;i--) {
		if(L[i]==MAL || ma[L[i]+1]>H[i]) {
			step[L[i]]++;
			ok[i]=1;
			ma[L[i]]=max(ma[L[i]],H[i]);
		}
	}
	
	FOR(i,M) cin>>x>>y, E[x-1].push_back({y,i});
	
	LIS=vector<int>(N+1,1<<30);
	LIS[0]=0;
	FOR(i,N) {
		FORR(r,E[i]) R[r.second]=lower_bound(LIS.begin(),LIS.end(),r.first) - LIS.begin();
		LIS[L[i]] = H[i];
	}
	LIS=vector<int>(N+1,1<<30);
	LIS[0]=-1<<30;
	for(i=N-1;i>=0;i--) {
		FORR(r,E[i]) R[r.second]+=lower_bound(LIS.begin(),LIS.end(),-r.first) - LIS.begin()-1;
		FORR(r,E[i]) R[r.second]=max(R[r.second],MAL-(ok[i]&&step[L[i]]==1));
		x=lower_bound(LIS.begin(),LIS.end(),-H[i]) - LIS.begin();
		LIS[x]=-H[i];
	}
	
	FOR(i,M) _P("%d\n",R[i]);
	
}

まとめ

C,DはB,Cでもよさそうな難易度だったな。