結果

問題 No.2170 Left Addition Machine
ユーザー rin204
提出日時 2022-11-28 21:36:18
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 664 ms / 2,000 ms
コード長 992 bytes
コンパイル時間 4,914 ms
コンパイル使用メモリ 200,304 KB
最終ジャッジ日時 2025-02-09 01:55:01
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 69
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/segtree>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
using ll = long long;
const int N = 200200;
mint pow2[N];

struct S{
	ll l;
	ll r;
	int size;
	mint ans;
	int anssize;
};

S op(S l, S r){
	if(l.size == -1) return r;
	else if(r.size == -1) return l;
	S ret;
	ret.l = l.l;
	ret.r = r.r;
	ret.size = l.size + r.size;
	if(r.size != r.anssize || l.r >= r.l){
		ret.ans = r.ans;
		ret.anssize = r.anssize;
	}
	else{
		ret.ans = l.ans + (2 * r.ans - r.l) * pow2[l.anssize - 1];
		ret.anssize = l.anssize + r.size;
	}
	return ret;
}

S e(){
	return S{0, 0, -1, 0, 0};
}

int main(){
	pow2[0] = 1;
	for(int i = 1; i < N; i++) pow2[i] = pow2[i - 1] * 2;
	int n, Q;
	cin >> n >> Q;
	vector<S> A(n);
	ll a;
	for(int i = 0; i < n; i++){
		cin >> a;
		A[i] = S{a, a, 1, a, 1};
	}
	segtree<S, op, e> seg(A);
	int l, r;
	while(Q--){
		cin >> l >> r;
		cout << seg.prod(l - 1, r).ans.val() << endl;
	}

}
0