Codeforces #759 : Div2 F. Non-equal Neighbours

典型だったりするのかな。
https://codeforces.com/contest/1591/problem/F

問題

N要素の整数列Aが与えられる。
以下を満たす整数列Bは何通りか。

• 1≦B[i]≦A[i]
• B[i] != B[i+1]

解法

包除原理の応用で、同じ値を持つ連続区間の個数が偶奇のケースを数え上げる。
dp[i][b] := i番目までのprefixの値を定めたとき、同じ値を持つ連続区間の個数の偶奇がbに一致するケースの数

とする。区間[j,i]で同じ値を取ると、
dp[i][b] += dp[j-1][b^1] * min(A[j],...,A[i])
と遷移する。
i,jを総当たりするとO(N^2)かかるが、min(A[j],...,A[i])が同じ区間をスタックの要領でまとめて計算すると均してO(N)で済む。

int N;
int A[501010];
ll dp[505050][2];
const ll mo=998244353;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	vector<pair<int,ll>> S[2];
	ll sum[2]={};
	dp[0][0]=1;
	
	FOR(i,N) {
		cin>>A[i];
		
		FOR(j,2) {
			ll ts=0;
			while(S[j].size()&&S[j].back().first>A[i]) {
				sum[j]+=mo-S[j].back().second;
				ts+=S[j].back().second*A[i]%mo*modpow(S[j].back().first)%mo;
				S[j].pop_back();
			}
			dp[i+1][j^1]=(ts+sum[j]+dp[i][j^1]*A[i])%mo;
			S[j].push_back({A[i],(ts+dp[i][j^1]*A[i])%mo});
			(sum[j]+=ts+dp[i][j^1]*A[i])%=mo;
		}
		swap(S[0],S[1]);
		swap(sum[0],sum[1]);
	}
	
	cout<<(dp[N][0]+mo-dp[N][1])%mo<<endl;
}

まとめ

これ典型で他でも出そうだな…。