Codeforces #873 : Div1 B2. Range Sorting (Hard Version)

不参加だった回。
https://codeforces.com/contest/1827/problem/B2

問題

ある数列Pの美しさは、以下のように定義される。

• Pのうち長さLの部分列をソートするのにL秒かかる
• P全体をソートするのにかかる最小時間が美しさ

整数列Aが与えられる。
Aの各部分列における美しさの総和を求めよ。

解法

A[i]とA[i+1]を含むソートが生じるのは、A[i]とA[i+1]を含む部分列のうち、A[i]以前の最大値が、A[i+1]以降の最小値より大きい場合である。
これを小さい順に数え上げて行こう。

int T,N,A[303030];

int L[303030],R[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		vector<pair<int,int>> V;
		FOR(i,N) {
			cin>>A[i];
			V.push_back({A[i],i});
		}
		ll sum=0;
		for(i=1;i<=N;i++) sum+=1LL*(i-1)*(N+1-i);
		sort(ALL(V));
		set<int> L={-1,N},M={-1,N};
		FOR(i,N) M.insert(i);
		
		FORR2(a,b,V) {
			M.erase(b);
			int k=*prev(L.lower_bound(b));
			int x=*prev(M.lower_bound(k+1));
			int y=*L.lower_bound(b);
			sum-=1LL*(k-x)*(y-b);
			
			L.insert(b);
		}
		cout<<sum<<endl;
	}
}

まとめ

コードは短い。