Codeforces ECR #160 : D. Array Collapse

割と苦戦してるな…。
https://codeforces.com/contest/1913/problem/D

問題

値が相異なる数列Aが与えられる。
Aの連続部分列を選び、最小値を除いて削除する、という処理を任意回数行える時、最終的にAとしてあり得るのは何通りか。

解法

以下を考える。
f(L,R) := A[L...R]内の要素を1個以上消す場合、最終的にどう残すかの組み合わせ数。なお、A[L-1]やA[R+1]はAの範囲外か、またはA[L...R]より小さい値で残すことが確定している

A[L...R]の最小値をA[M]としたとき、A[M]を残すか残さないかで分岐しよう。

• 残す場合、f(L,R)に(1+f(L,M-1))*(1+f(M+1,R))だけ計上する
• 残さない場合、A[L...M]かA[M...R]は消しきらないといけないので、f(L,M-1)+f(M+1,R)だけ計上する。

int T,N;
int P[303030];
ll TL[303030],TR[303030];
const ll mo=998244353;

template<class V,int NV> class SegTree_Pair {
public:
	vector<pair<V,int> > val;
	static V const def=1<<30;
	pair<V,int> comp(pair<V,int> l,pair<V,int> r){ return min(l,r);}
	SegTree_Pair(){
		val.resize(NV*2);
		int i;
		FOR(i,NV) val[i+NV]=make_pair(def,i);
		for(i=NV-1;i>=1;i--) val[i]=comp(val[2*i],val[2*i+1]);
	};
	pair<V,int> getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return make_pair(def,NV);
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=make_pair(v,entry-NV);
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

SegTree_Pair<int,1<<20> st;
map<pair<int,int>,ll> memo;

ll dfs(int L,int R) {
	//1個以上残す
	if(R<L) return 0;
	if(memo.count({L,R})) return memo[{L,R}];
	pair<int,int> p=st.getval(L,R+1);
	int M=p.second;
	
	ll ret=0;
	if(L==0) {
		//Mを消す
		ret+=dfs(L,M-1);
	}
	else if(R==N-1) {
		//Mを消す
		ret+=dfs(M+1,R);
	}
	else {
		//左を残す
		ret+=dfs(L,M-1)+dfs(M+1,R);
	}
	//Mを残す
	ret+=(1+dfs(L,M-1))*(1+dfs(M+1,R));
	
	return memo[{L,R}]=ret%mo;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			cin>>P[i];
			st.update(i,P[i]);
		}
		memo.clear();
		
		pair<int,int> p=st.getval(0,N);
		ll ret=(1+dfs(0,p.second-1))*(1+dfs(p.second+1,N-1))%mo;
		cout<<ret<<endl;
		
	}
}

まとめ

Aは順列でもいい気がするけど…。