はまやんはまやんはまやん

hamayanhamayan's blog

CardShuffle [yukicoder No.619]

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());
        }
    }
}