長さ の非負整数列 と、R, G, B からなる長さ の文字列 が与えられます。次の 2 種類のクエリを合計 個処理する問題です()。
1 i x: を に変更する。2 l r: かつ がこの順にR,G,Bである組 すべてについての の総和を、 で割った余りを出力する。
セグメント木の各ノードに、担当区間について次の 6 つの値を持たせます。
- : が
Rである についての の総和(G,Bについても同様に , ) - : かつ がこの順に
R,Gである組についての の総和( も同様) - :求めたい値
隣り合う区間 (左)と (右)をつなげるとき、たとえば になる組は「両方 の中」「両方 の中」「R が 、G が 」のどれかです。最後の場合の総和は なので、次のように合成できます。
, , はそれぞれの和です。これをセグメント木に載せれば、全体の計算量は です。
C++
#include "shogo-library/base/all"#include "shogo-library/data_structures/segtree.hpp"#include "shogo-library/math/modint.hpp"using mint = modint998244353;
enum E { R, G, B, RG, GB, RGB,};
void solve() { LL(N, Q); VL(A, N); STR(S); struct AALC0001E { struct S { ary<mint, 6> cnt; S() : cnt{} {} S(char x, mint a) : cnt{} { if (x == 'R') { cnt[E::R] += a; } else if (x == 'G') { cnt[E::G] += a; } else if (x == 'B') { cnt[E::B] += a; } else { assert(false); } } }; static S op(const S &a, const S &b) { S res = S(); res.cnt[E::R] = a.cnt[E::R] + b.cnt[E::R]; res.cnt[E::G] = a.cnt[E::G] + b.cnt[E::G]; res.cnt[E::B] = a.cnt[E::B] + b.cnt[E::B]; res.cnt[E::RG] = a.cnt[E::RG] + b.cnt[E::RG] + a.cnt[E::R] * b.cnt[E::G]; res.cnt[E::GB] = a.cnt[E::GB] + b.cnt[E::GB] + a.cnt[E::G] * b.cnt[E::B]; res.cnt[E::RGB] = a.cnt[E::RGB] + b.cnt[E::RGB] + a.cnt[E::RG] * b.cnt[E::B] + a.cnt[E::R] * b.cnt[E::GB]; return res; } static S e() { return S(); } }; vec<AALC0001E::S> init; init.reserve(N); rep(i, N) init.emplace_back(S[i], A[i]); SegTree<AALC0001E> seg(init); rep(Q) { LL(q); if (q == 1) { LL(i, x); seg.set(i - 1, {S[i - 1], x}); } else if (q == 2) { LL(l, r); print(seg.prod(l - 1, r).cnt[E::RGB]); } }}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}SegTree には、要素の型 S、演算 op、単位元 e をまとめた構造体を渡します。6 つの値は enum E の名前で配列 cnt に入れています。
使用ライブラリ:cpp_include@402f0cf