yukicoder : No.1827 最長部分スーパーリッチ門松列列

実装に手間取った。
https://yukicoder.me/problems/no/1827

問題

1～NのPermutation Pが与えられる。
Pの部分列のうち、以下を満たす最長の数列の長さを求めよ。

• 偶数番目の要素の最小値が、奇数番目の要素の最大値よりも大きいか、奇数番目の要素の最小値が、偶数番目の要素の最大値よりも大きいか

解法

区間[1,N]について、i∈[L,R]に対しP[i]≦xであるような区間[L,R]の集合をA,P[i]＞xであるような区間の集合をBとする。
その際、A,B内は、AとBで全区間をカバーしつつ、重複した区間を持たないようにして最小要素数を取るようにする。
この時、各区間から1個ずつ要素を選んで並べると、問題の条件を満たす数列が作れる。
よって|A|+|B|が解の候補となる。

あとは、xを1つずつずらしながらA,Bを更新していき、そのつど|A|+|B|を求めよう。

int T,N;
int P[505050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			cin>>x;
			P[x]=i;
		}
		set<pair<int,int>> up,down;
		up.insert({-1,-1});
		up.insert({N,N});
		down.insert({-1,N});
		int ma=1;
		for(i=N;i>=1;i--) {
			x=P[i];
			auto it=down.lower_bound({x+1,x+1});
			it--;
			auto p=*it;
			down.erase(p);
			
			if(p.first<x) down.insert({p.first,x-1});
			if(p.second>x) down.insert({x+1,p.second});
			
			
			up.insert({x,x});
			it=up.lower_bound({x,x});
			if(next(it)->first==x+1) {
				p=*next(it);
				p.first=x;
				up.erase(next(it));
				up.erase({x,x});
				up.insert(p);
			}
			
			it=up.lower_bound({x,x});
			if(prev(it)->second==x-1) {
				y=it->second;
				p=*prev(it);
				up.erase(it);
				up.erase(p);
				p.second=y;
				up.insert(p);
			}
			
			x=up.size();
			if(up.begin()->second==-1) x--;
			if(up.rbegin()->first==N) x--;
			y=down.size();
			if(down.begin()->second==-1) y--;
			if(down.rbegin()->first==N) y--;
			
			ma=max(ma,x+y);
		}
		
		cout<<ma<<endl;
	}
}

まとめ

区間の集合を管理するの、面倒で苦手なんだよな。