結果
問題 |
No.2170 Left Addition Machine
|
ユーザー |
👑 ![]() |
提出日時 | 2022-12-22 00:15:01 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 115 ms / 2,000 ms |
コード長 | 3,857 bytes |
コンパイル時間 | 2,883 ms |
コンパイル使用メモリ | 121,272 KB |
最終ジャッジ日時 | 2025-02-09 18:17:17 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 69 |
ソースコード
#line 1 "Main.cpp" #include <iostream> #include <string> #include <vector> #include <algorithm> #include <utility> #include <atcoder/modint> #line 2 "nachia\\set\\word-size-tree.hpp" #line 5 "nachia\\set\\word-size-tree.hpp" namespace nachia{ struct WordsizeTree{ using Word = unsigned long long; static constexpr unsigned int W = 64; int N; std::vector<std::vector<Word>> A; static int highBit(Word x){ if(x == 0) return 0; return W-1 - __builtin_clzll(x); } static int lowBit(Word x){ if(x == 0) return W; return __builtin_ctzll(x); } WordsizeTree(unsigned int length){ N = length; int n = length; do { std::vector<Word> a(n/W+1,0); A.emplace_back(std::move(a)); n /= W; } while(n); } WordsizeTree(const std::string& binStr = ""){ N = binStr.size(); int n = N; { std::vector<Word> a(n/W+1); for(int i=0; i<n; i++) if(binStr[i] == '1'){ a[i/W] |= (Word)1 << (i%W); } A.emplace_back(std::move(a)); n /= W; } while(n){ std::vector<Word> a(n/W+1,0); for(int i=0; i<=n; i++){ if(A.back()[i]) a[i/W] |= (Word)1 << (i%W); } A.emplace_back(std::move(a)); n /= W; } } void insert(int x){ for(auto& a : A){ a[x/W] |= (Word)1 << (x % W); x /= W; } } void erase(int x){ for(auto& a : A){ a[x/W] &= ~((Word)1 << (x % W)); if(a[x/W]) return; x /= W; } } int count(int x) const { return (int)((A[0][x/W] >> (x%W)) & 1); } int noLessThan(int x) const { int d = 0, i = x; while(true){ if(d >= (int)A.size()) return -1; if(i/W >= (int)A[d].size()) return -1; Word m = A[d][i/W] & ((~(Word)0) << (i%W)); if(!m){ d++; i /= W; i++; } else{ int to = lowBit(m); i = i/W*W + to; if(d == 0) break; i *= W; d--; } } return i; } int noGreaterThan(int x) const { int d = 0, i = x; while(true){ if(i < 0) return -1; if(d >= (int)A.size()) return -1; Word m = A[d][i/W] & ~((~(Word)1) << (i%W)); if(!m){ d++; i /= W; i--; } else{ int to = highBit(m); i = i/W*W + to; if(d == 0) break; i *= W; i += W-1; d--; } } return i; } }; } // namespace nachia #line 8 "Main.cpp" using namespace std; using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; #define rep(i,n) for(int i=0; i<(int)(n); i++) const i64 INF = 1001001001001001001; using Modint = atcoder::static_modint<998244353>; int main(){ int N, Q; cin >> N >> Q; vector<int> A(N); rep(i,N) cin >> A[i]; vector<Modint> B(N); rep(i,N) B[i] = Modint::raw(A[i]); vector<Modint> sumB(N+1); for(int i=N-1; i>=0; i--) sumB[i] = sumB[i+1] + sumB[i+1] + B[i]; vector<Modint> pow2(N+1); pow2[0] = 1; for(int i=1; i<=N; i++) pow2[i] = pow2[i-1] + pow2[i-1]; nachia::WordsizeTree S(N); rep(i,N-1) if(A[i] >= A[i+1]) S.insert(i); rep(i,Q){ int l, r; cin >> l >> r; l--; l = max(l, S.noGreaterThan(r-2) + 1); Modint ans = sumB[l+1] - sumB[r] * pow2[r-l-1] + B[l]; cout << ans.val() << '\n'; } return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } } ios_do_not_sync_instance;