yukicoder : No.2170 Left Addition Machine

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

問題

整数列Bに対し、以下の手順を要素が1つになるまで行う。

• Bの中で最大値を取る要素B[i]を選ぶ。複数あるならindexが最小のものを選ぶ。
• j＜iに対し、B[j]+=B[i]としたうえでB[i]を削除する。

整数列Aが与えられる。
クエリとして部分列の範囲が指定されるので、以下の問いに答えよ。

• Bとしてクエリで与えられたAの部分列を取ったとする。上記手順を行ったとき、Bに最後に残る値は何か。

解法

B[i]≧B[j]かつi＜jの時、B[j]より先にB[0...i]が消えるし、B[0..i]の値はB[j]に寄与しない。
よってそのようなB[0...i]はないとしてよい。
と考えると、まず解に寄与するのはBの末尾のうち真に単調増加な最長suffixである。

よってそこだけ抜き出したBを考える。
あとは、B[0]+sum(2^(i-1)*B[i])が解となる。
これは2^i*A[i]の累積和をもっておけば高速に算出可能である。

int N,Q;
ll A[202020];
const ll mo=998244353;

int NG[202020];
ll S[202020];
ll MS[202020];
ll p2[202020],r2[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p2[0]=r2[0]=1;
	FOR(i,201010) {
		p2[i+1]=p2[i]*2%mo;
		r2[i+1]=r2[i]*(mo+1)/2%mo;
	}
	
	cin>>N>>Q;
	FOR(i,N) {
		cin>>A[i];
		if(i&&A[i]>A[i-1]) {
			NG[i]=NG[i-1];
		}
		else {
			NG[i]=i;
		}
		S[i+1]=(S[i]+A[i])%mo;
		MS[i+1]=(MS[i]+p2[i]*A[i])%mo;
	}
	while(Q--) {
		int L,R;
		cin>>L>>R;
		L--,R--;
		L=max(NG[R],L);
		ll ret=(MS[R+1]-MS[L+1]+mo)*r2[L+1]+A[L];
		cout<<ret%mo<<endl;
		
	}
	
}

まとめ

★3でもよいかも。