DISCO! [DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦 D]

https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_d

前提知識

• 半環問題

解説

https://atcoder.jp/contests/ddcc2019-final/submissions/4045056

これはやったことが無いと解くのは難しい。
半環問題というのがある。
（正直自分は半環というのをちゃんと理解してないので、正確な表現ではないかもしれない）
この半環問題を解くためにはDPを行列で更新するということに慣れる必要がある。
それに慣れていない場合は、行列累乗による動的計画法高速化を先に勉強することを勧める。
以下、その知識はある前提で説明する。
　
クエリ無しでまずは考える。
dp[i][lst] := i番目の文字まで見ていて、discoのlst番目までできている部分文字列の組み合わせ
このdpを考える。このdpの更新式は
// 後ろに文字を追加しない
dp[i+1][lst] = dp[i][lst]
// discoのc+1番目とi+1番目の文字が等しい場合。最後にdiscoのc+1番目を追加して部分文字列を作る
dp[i+1][c+1] = dp[i][c]
これは行列で表現することができる。
dp[i]→dp[i+1]への遷移に使う行列をm[i]とする。
すると、dp[0]からdp[i]への遷移は順番にm[0], m[1], ..., m[i-1]を使って遷移させる。
行列は、行列だけ先に計算することができるので、m[0]～m[i-1]を計算して、dp[0]と掛け合わせることでも答えが得られる。
この性質をうまく使って、もともとの問題を解く。
　
セグメントツリーに行列を乗せる。
行列を乗せて、計算を行列の積にすることで任意の区間の行列の積が求められる。
クエリ毎に使う行列の積を取ってきて、dp[0]とかけ合わせれば答えが得られる。
　
注意点がいくつかある。
1. 計算時間が結構厳しいので、mod2^32をうまく使うことで剰余計算をなくそう（剰余計算は重い）
unsigned intを使うことで、オーバーフローがちょうどmod2^32になるので、剰余計算を入れる必要がなくなる。
2. セグメントツリーに行列を乗せるが左右が重要なので注意する
自分の実装では左右逆でマージしている

typedef unsigned int mint;
struct func {
    mint m[6][6];
    func(){
        rep(i, 0, 6) rep(j, 0, 6) m[i][j] = 0;
        rep(i, 0, 6) m[i][i] = 1;
    }
    func(int c) {
        rep(i, 0, 6) rep(j, 0, 6) m[i][j] = 0;
        rep(i, 0, 6) m[i][i] = 1;
        m[c + 1][c] = 1;
    }
};
func operator*(func y, func x) {
    
    func res;
    rep(i, 0, 6) rep(j, 0, 6) res.m[i][j] = 0;
    rep(i, 0, 6) rep(j, 0, 6) rep(k, 0, 6) {
        res.m[i][j] = res.m[i][j] + x.m[i][k] * y.m[k][j];
    }
    return res;
}
//---------------------------------------------------------------------------------------------------
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]); }
};



string S; int Q;
int N;
SegTree<func, 1 << 20> st;
string disco = "DISCO";
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> Q;
    N = S.length();
 
    map<char, int> dic;
    rep(i, 0, 5) dic[disco[i]] = i;
 
    rep(i, 0, N) st.update(i, func(dic[S[i]]));
    rep(q, 0, Q) {
        int L, R; cin >> L >> R; L--;
 
        auto f = st.get(L, R);
 
        mint v[6], vv[6];
        rep(i, 0, 6) v[i] = vv[i] = 0;
        v[0] = 1;
 
        rep(i, 0, 6) rep(j, 0, 6) {
            vv[i] = vv[i] + f.m[i][j] * v[j];
        }
 
        printf("%u\n", vv[5]);
    }
}