AtCoder ARC #115 : E - LEQ and NEQ

どうも考察が甘くて行けないなぁ…。
https://atcoder.jp/contests/arc115/tasks/arc115_e

問題

N要素の整数列Aが与えられる。
整数列Bを作るとき、1≦B[i]≦A[i]かるB[i]!=B[i+1]を満たすのは何通りか。

解法

以下を考える。
dp(n,k) := Bの先頭n要素を定めたとき、各実にB[i]=B[i+1]である場所がk箇所ある
すると解は包除原理の要領でsum*1となる。

dp(n,k)に対し、B[n+1]～B[m]を同じ値にすることで、dp(m,k+(m-(n+1))+=min(B[(n+1)...m])*dp(n,k)という遷移をすることができる。
ただこれを愚直に行うとO(N^2)かかる。
実質kは偶奇しか考慮しなくてよい。
あとはmin(B[(n+1)...m])*dp(n,k)の部分をスタックなど使いmin(B[(n+1)...m])を更新しながら累積和を計算していくとよい。

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;
}

まとめ

本番SegTree解も考えたんだけど、綺麗に書けなかったんだよね。

*1:-1)^k*dp(n,k