yukicoder : No.2433 Min Increasing Sequence

これは割とすんなり。
https://yukicoder.me/problems/no/2433

問題

N要素の整数列Aが与えられる。
これをいくつかの連続な部分列に分割したとき、各部分列の最小値を並べた数列が単調増加となるようにしたい。
条件を満たす分割方法は、2^(N-1)通りのうち何通りか。

解法

A[i]がA[i]～A[N-1]のうち最小値となるようなiを並べた数列をBとする。

B[i]とB[i+1]の間に、2個以上分割した境界があってはならない。
逆に1個までなら分割を入れてよいので、(B[i+1]-B[i]+1)の積を取ればよい。

int N;
ll A[202020];
const ll mo=998244353;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<ll> X;
	FOR(i,N) {
		cin>>A[i];
	}
	vector<int> V;
	V.push_back(N-1);
	for(i=N-1;i>=0;i--) {
		if(A[i]<=A[V.back()]) V.push_back(i);
	}
	reverse(ALL(V));
	ll ret=1;
	
	FOR(i,V.size()-1) {
		ret=ret*(V[i+1]-V[i]+1)%mo;
	}
	cout<<ret<<endl;
	
}

まとめ

実装は軽いね。