https://yukicoder.me/problems/no/619
前提知識
解法
https://yukicoder.me/submissions/226108
セグメントツリーを使って解く。
公式解説を見てしまったので、その実装例として下のセグメントツリーを見て欲しい。
struct func { mint a, b, c; int f; func(mint a = 1, mint b = 0, mint c = 0, int f = 0) : a(a), b(b), c(c), f(f) {} }; func operator*(func x, func y) { // op1 if (x.f and y.f) return func(x.a, x.b + x.c * y.a + y.b, y.c, 1); // op2 if (x.f) return func(x.a, x.b, x.c * y.a, 1); // op3 if (y.f) return func(x.a * y.a, y.b, y.c, 1); // op4 if (!x.f and !y.f) return func(x.a * y.a, 0, 0, 0); assert(0); } //--------------------------------------------------------------------------------------------------- template<class V, int NV> struct SegTree { // [L,R) V comp(V l, V r) { return l * r; }; vector<V> val; SegTree() { val = vector<V>(NV * 2); } V get(int x, int y, int l = 0, int r = NV, int k = 1) { if(r<=x||y<=l)return V();if(x<=l&&r<=y)return val[k];auto A=get(x,y,l,(l+r)/2,k*2); auto B = get(x,y,(l+r)/2,r,k*2+1);return comp(A,B);} void update(int i, V v){i+=NV;val[i]=v;while (i>1)i>>=1,val[i]=comp(val[i*2],val[i*2+1]);}};
あとは、これを使って更新したり処理したりするだけ。
注意点がある。
「+?」「*?」でセグメントツリーに載せているが、取得区間の最初が「*?」だと上手く行かない。
その場合は、一時的に「+?」に直して取得して、取得後戻そう。
int N; int A[101010]; char B[101010]; int Q; SegTree<func, 1 << 17> st; //--------------------------------------------------------------------------------------------------- void update(int i) { if (B[i] == '*') st.update(i, func(A[i], 0, 0, 0)); else st.update(i, func(1, 0, A[i], 1)); } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; cin >> A[0]; B[0] = '+'; rep(i, 0, N / 2) cin >> B[i + 1] >> A[i + 1]; rep(i, 0, N / 2 + 1) update(i); cin >> Q; rep(q, 0, Q) { string s; int x, y; cin >> s >> x >> y; if (s == "!") { if (x % 2 == 1) { x /= 2; y /= 2; swap(A[x], A[y]); update(x); update(y); } else { x /= 2; y /= 2; swap(B[x], B[y]); update(x); update(y); } } else { x /= 2; y /= 2; func f; if (B[x] == '*') { B[x] = '+'; update(x); f = st.get(x, y + 1); B[x] = '*'; update(x); } else f = st.get(x, y + 1); mint ans = f.b + f.c; printf("%d\n", ans.get()); } } }