コンテンツにスキップ

AALC001 E - RGB

サイト
AtCoder
コンテスト
AALC001
問題
E - RGB
難易度
-

長さ NN の非負整数列 AA と、R, G, B からなる長さ NN の文字列 SS が与えられます。次の 2 種類のクエリを合計 QQ 個処理する問題です(1≤N,Q≤2×1051 \le N, Q \le 2 \times 10^5)。

  • 1 i x:AiA_i を xx に変更する。
  • 2 l r:l≤i<j<k≤rl \le i < j < k \le r かつ Si,Sj,SkS_i, S_j, S_k がこの順に R, G, B である組 (i,j,k)(i, j, k) すべてについての AiAjAkA_i A_j A_k の総和を、998244353998244353 で割った余りを出力する。

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

  • R\mathrm{R}:SiS_i が R である ii についての AiA_i の総和(G, B についても同様に G\mathrm{G}, B\mathrm{B})
  • RG\mathrm{RG}:i<ji < j かつ Si,SjS_i, S_j がこの順に R, G である組についての AiAjA_i A_j の総和(GB\mathrm{GB} も同様)
  • RGB\mathrm{RGB}:求めたい値

隣り合う区間 XX(左)と YY(右)をつなげるとき、たとえば RG\mathrm{RG} になる組は「両方 XX の中」「両方 YY の中」「R が XX、G が YY」のどれかです。最後の場合の総和は RXGY\mathrm{R}^X \mathrm{G}^Y なので、次のように合成できます。

RGXY=RGX+RGY+RXGYGBXY=GBX+GBY+GXBYRGBXY=RGBX+RGBY+RGXBY+RXGBY\begin{aligned} \mathrm{RG}^{XY} &= \mathrm{RG}^X + \mathrm{RG}^Y + \mathrm{R}^X \mathrm{G}^Y \\ \mathrm{GB}^{XY} &= \mathrm{GB}^X + \mathrm{GB}^Y + \mathrm{G}^X \mathrm{B}^Y \\ \mathrm{RGB}^{XY} &= \mathrm{RGB}^X + \mathrm{RGB}^Y + \mathrm{RG}^X \mathrm{B}^Y + \mathrm{R}^X \mathrm{GB}^Y \end{aligned}

R\mathrm{R}, G\mathrm{G}, B\mathrm{B} はそれぞれの和です。これをセグメント木に載せれば、全体の計算量は 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;
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