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; }
まとめ
今回しょうもないミスを重ねてしまった。