Dangerous Hopscotch [「みんなのプロコン 2019」決勝 D]

https://atcoder.jp/contests/yahoo-procon2019-final/tasks/yahoo_procon2019_final_d

前提知識

• 半環問題

解説

https://atcoder.jp/contests/yahoo-procon2019-final/submissions/4353743

半環をSegtreeであつかうテクを使う。
このテクを知らない場合は、先に他で学習しよう。
今回の問題は座圧が含まれるので、学習には適さない。
　
dp[i] := i個前にいる組合せ
とすると、
次の位置に石が無いなら、
dp'[0] = dp[0] + dp[1]
dp'[1] = dp[0]
次の位置に石があるなら、
dp'[0] = 0;
dp'[1] = dp[0]
となる。
この更新は行列で表現できる。
「2 l r」については、Segtreeで対応する区間の行列積を取ってくれば答えられる。
今回はNが大きいので、座圧してSegtreeに入れ込む必要がある。
　
dicには座圧した座標が入っているものとする。
Segtreeには行列を乗せるが、「st[i] := dic[i]からdic[i+1]に移る場合の遷移用行列」として乗せる。
乗せる中身は、{{1 1}, {1, 0}}^(dic[i+1]-dic[i])を乗せればいい。
この累乗は繰り返し二乗法で高速化する。
もしdic[i+1]に石がある場合は繰り返し二乗法をした結果のdp'[0] = dp[0] + dp[1]をdp'[0] = 0;に変換する。
この行列作成はget関数で行っている。
　
これで準備ができたので、後はクエリ先読みして、座圧をして、処理していけばいい。
この辺は半環問題が理解できていればさほど難しくはない。

int N, Q;
int T[101010], X[101010], Y[101010];
int A[201010];
SegTree<func, 1 << 18> st;
//---------------------------------------------------------------------------------------------------
vector<int> dic;
func get(int len, int stone) {
    func f(0), x(0);
    func ret;
    while (0 < len) {
        if ((len % 2) == 0) x = mul(x, x), len >>= 1;
        else ret = mul(ret, x), --len;
    }
    if (stone == 1) {
        ret.m[0][0] = 0;
        ret.m[0][1] = 0;
    }
    return ret;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
 
    rep(i, 0, Q) {
        cin >> T[i];
        if (T[i] == 1) {
            cin >> X[i];
            dic.push_back(X[i]);
        }
        else {
            cin >> X[i] >> Y[i];
            dic.push_back(X[i]);
            dic.push_back(Y[i]);
        }
    }
 
    sort(all(dic));
    dic.erase(unique(all(dic)), dic.end());
 
    int n = dic.size();
    rep(i, 0, n - 1) {
        st.update(i, get(dic[i + 1] - dic[i], 0));
    }
 
    // st[i] := dic[i] -> dic[i+1]
 
    rep(q, 0, Q) {
        int t; t = T[q];
        if (t == 1) {
            int p = X[q];
            p = lower_bound(all(dic), p) - dic.begin();
 
            if (A[p] == 0) {
                A[p] = 1;
                if(0 < p) st.update(p-1, get(dic[p]-dic[p-1], A[p]));
            }
            else {
                A[p] = 0;
                if (0 < p) st.update(p-1, get(dic[p] - dic[p - 1], A[p]));
            }
        }
        else {
            int l, r; l = X[q], r = Y[q];
 
            l = lower_bound(all(dic), l) - dic.begin();
            r = lower_bound(all(dic), r) - dic.begin();
 
            if (A[l] == 1) {
                printf("0\n");
                continue;
            }
 
            func f = st.get(l, r);
 
            printf("%d\n", f.m[0][0].get());
        }
    }
}