コンテンツにスキップ

AALC001 H - Add and Mod

サイト
AtCoder
コンテスト
AALC001
問題
H - Add and Mod
難易度
-

長さ NN の非負整数列 AA に対して、次の 2 種類のクエリを合計 QQ 個処理する問題です(1≤N,Q≤2×1051 \le N, Q \le 2 \times 10^5)。

  • 1 i x:AiA_i を xx に変更する。
  • 2 l r x:i=l,…,ri = l, \dots, r の順に、Ai=0A_i = 0 なら x←x mod 998244353x \leftarrow x \bmod 998244353、Ai>0A_i > 0 なら x←x+Aix \leftarrow x + A_i とする。最終的な xx を出力する。

p=998244353p = 998244353 とします。区間 [l,r][l, r] に 00 が含まれないなら、答えは x+∑i=lrAix + \sum_{i=l}^{r} A_i です。

00 が含まれる場合、最後の 00 の位置を mm とします。途中で pp で割った余りをとっても、その後の値を pp で割った余りは変わりません。位置 mm では余りをとるので、その時点の値は (x+∑i=lm−1Ai) mod p\left(x + \sum_{i=l}^{m-1} A_i\right) \bmod p になります。その後は ∑i=m+1rAi\sum_{i=m+1}^{r} A_i を足すだけです。

そこで、セグメント木の各ノードに担当区間について次の値を持たせます。

  • XX:00 を含むかどうかと、含む場合は最後の 00 より前の要素の和を pp で割った余り
  • YY:最後の 00 より後の要素の和(00 を含まなければ区間全体の和)

隣り合う区間 LL(左)と RR(右)をつなげるとき、RR が 00 を含むなら、最後の 00 は RR の中にあります。その前の要素は LL 全体と RR の最後の 00 より前の部分なので、X=(L の総和+XR) mod pX = (L \text{ の総和} + X^R) \bmod p、Y=YRY = Y^R です。LL の総和を pp で割った余りは、LL が 00 を含むかどうかによらず XL+YLX^L + Y^L で求まります(00 を含まないなら XLX^L を 00 とみなします)。RR が 00 を含まないなら、X=XLX = X^L、Y=YL+YRY = Y^L + Y^R です。

答えは、区間が 00 を含むなら (x+X) mod p+Y(x + X) \bmod p + Y、含まなければ x+Yx + Y です。YY は最大で 2×105×109=2×10142 \times 10^5 \times 10^9 = 2 \times 10^{14} 程度なので、64 ビット整数に収まります。全体の計算量は O(N+Qlog⁡N)O(N + Q \log N) です。

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 をまとめた構造体を渡します。上の XX を std::optional<mint> の x で表し、00 を含まないことを値がないことで表しています。YY は ll の y です。

使用ライブラリ:cpp_include@402f0cf