Replace Digits [ACL Beginner Contest E]

https://atcoder.jp/contests/abl/tasks/abl_e

前提知識

• 遅延評価セグメントツリー

解説

https://atcoder.jp/contests/abl/submissions/17051206

ACLコンテストというのもあり、遅延評価セグメントツリーが真っ先に思いついた。
遅延評価セグメントツリーで解くんだろうなぁと思って考えると、解ける。
遅延評価セグメントツリーの細かい解説はしないので、どこかで勉強してきてほしい。
それが分かっていれば、この問題はそれほど難しくない。

区間にどういう情報を持たせるか

セグメントツリーで解くということは、区間のマージをする必要があるが、どういう情報を持つべきだろうか。
一般的に答えがそのまま情報として持たれている場合が多いので、とりあえずそれは入れておく。

• a: 区間を10進数として見たときの整数 (mod)

だが、これだけでは区間をマージするときにできない。
例えば、11と22をマージすると、1122になる。
実際に計算に落としてみると、11*100+22となる。
ここで100という数字が出てくるが、これは10の22の桁数乗である。
このように右側の区間分ずらすために桁数乗も情報として必要のようだ

• a: 区間を10進数として見たときの整数 (mod)
• b: 10の桁数乗 (mod)

こうすれば(a,b)と(c,d)のマージは(ad+c,bd)で行えることと言える。
とりあえず遅延評価で更新していくことを抜きにすれば、クエリにこたえられそうだ。

遅延評価で何を伝搬させていくか

後は、遅延評価で何を伝搬させるかというところだが、普通に更新したい数を持たせればいい。
区間[L,R)に対してvで更新したい場合は、(v,10)の(R-L)乗を入れてやればいい。
これは繰り返し二乗法で毎回計算しても間に合う。

実装

自分のライブラリなので、雰囲気だが、こんな感じ。

const V def = make_pair(mint(0), mint(1)); int ldef = -1;  
V comp(V l, V r) {  
    return make_pair(l.first * r.second + r.first, l.second * r.second);  
}  
void setLazy(int i, int v) { lazy[i] = v; }  
void push(int k, int l, int r) {  
    if (lazy[k] != ldef) {  
        // modify------------------------------  
        dat[k] = make_pair(mint(lazy[k]), mint(10));  
        int kk = k;  
        while (kk < NV) {  
            kk = kk * 2;  
            dat[k] = comp(dat[k], dat[k]);  
        }  
        // ------------------------------------  
        if (r - l > 1) { setLazy(k * 2, lazy[k]); setLazy(k * 2 + 1, lazy[k]); }  
        lazy[k] = ldef;  
    }  
}  

int N, Q;
LazySegTree<1 << 18> st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    st.update(0, N, 1);
    rep(q, 0, Q) {
        int L, R, D; cin >> L >> R >> D;
        L--;
        st.update(L, R, D);
        int ans = st.get(0, N).first.get();
        printf("%d\n", ans);
    }
}