CSAcademy Round #62 : D. Partial Maximums

Aで手こずって微妙に順位に。
https://csacademy.com/contest/round-62/task/partial-maximums/

問題

N要素の整数列Aがある。
ここから1要素を除いたとき、i＜jならばA[i]＜A[j] となるようなjの数を最大化せよ。

解法

要は1要素を取り除いた後のLIS長を求める問題となる。
Aのprefixにおける要素の最大値およびLIS長と、suffixにおけるLIS長を求めよう。

次に取り除く要素を総当たりする。
A[i]を取り除く場合、A[i]以前のprefixで構成されるLIS長と、A[i+1]以降のうちmax(A[0..(i-1)])を始めて超える要素をA[j]とすると、A[j...(N-1)]のLIS長の和を求めればよい。
A[j]を求める作業は、スライド最大値+二分探索で行ける。

int N;
int V[201010];
vector<int> C;

int L[201010],R[201010];
int LN[201010],RN[201010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	int id=-1;
	FOR(i,N) {
		cin>>V[i];
		if(id==-1 || V[id]<V[i]) {
			L[i]=i;
			LN[i]=((id>=0)?LN[id]:0)+1;
			id=i;
		}
		else {
			L[i]=L[i-1];
			LN[i]=LN[i-1];
		}
	}
	vector<pair<int,int>> S;
	S.push_back({-1<<30,N});
	int ma=0;
	
	for(i=N-1;i>=0;i--) {
		x=lower_bound(ALL(S),make_pair((i)?-V[L[i-1]]:0,0))-S.begin()-1;
		
		int tmp=(i)?LN[i-1]:0;
		tmp+=RN[S[x].second];
		ma=max(ma,tmp);
		
		
		while(-S.back().first<=V[i]) S.pop_back();
		R[i]=S.back().second;
		RN[i]=RN[R[i]]+1;
		S.push_back({-V[i],i});
	}
	
	cout<<ma<<endl;
}

まとめ

今回しょうもないミスを重ねてしまった。