AALC001 H - Add and Mod
- サイト
- AtCoder
- コンテスト
- AALC001
- 問題
- H - Add and Mod
- 難易度
- -
長さ の非負整数列 に対して、次の 2 種類のクエリを合計 個処理する問題です()。
1 i x: を に変更する。2 l r x: の順に、 なら 、 なら とする。最終的な を出力する。
とします。区間 に が含まれないなら、答えは です。
が含まれる場合、最後の の位置を とします。途中で で割った余りをとっても、その後の値を で割った余りは変わりません。位置 では余りをとるので、その時点の値は になります。その後は を足すだけです。
そこで、セグメント木の各ノードに担当区間について次の値を持たせます。
- : を含むかどうかと、含む場合は最後の より前の要素の和を で割った余り
- :最後の より後の要素の和( を含まなければ区間全体の和)
隣り合う区間 (左)と (右)をつなげるとき、 が を含むなら、最後の は の中にあります。その前の要素は 全体と の最後の より前の部分なので、、 です。 の総和を で割った余りは、 が を含むかどうかによらず で求まります( を含まないなら を とみなします)。 が を含まないなら、、 です。
答えは、区間が を含むなら 、含まなければ です。 は最大で 程度なので、64 ビット整数に収まります。全体の計算量は です。
C++
#include "shogo-library/base/all"#include "shogo-library/data_structures/segtree.hpp"#include "shogo-library/math/modint.hpp"
using mint = modint998244353;
struct AALC0001H { struct S { std::optional<mint> x; ll y; S() : x{}, y{} {} S(ll f) : x{}, y{} { if (f == 0) x = 0; else y = f; } }; static S op(const S &a, const S &b) { S res = S{}; if (b.x.has_value()) { res.x = a.x.value_or(0) + a.y + b.x.value(); res.y = b.y; } else { res.x = a.x; res.y = a.y + b.y; } return res; } static S e() { return S(); }};
void solve() { LL(N, Q); VL(A, N); vec<AALC0001H::S> init; init.reserve(N); rep(i, N) init.emplace_back(A[i]); SegTree<AALC0001H> seg(init); rep(Q) { LL(q); if (q == 1) { LL(i, x); seg.set(i - 1, {x}); } else if (q == 2) { LL(l, r, x); auto p = seg.prod(l - 1, r); ll ans = x; if (p.x.has_value()) { ans = (ans + p.x.value()).value(); } ans += p.y; print(ans); } }}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}SegTree には、要素の型 S、演算 op、単位元 e をまとめた構造体を渡します。上の を std::optional<mint> の x で表し、 を含まないことを値がないことで表しています。 は ll の y です。
使用ライブラリ:cpp_include@402f0cf