裏紙

ほぼ競プロ、たまに日記

CF 712 E - Memory and Casinos

問題

Problem - E - Codeforces

問題概要

n個のカジノが一列に並んでいる(左からi番目のカジノをカジノiと呼ぶ)。カジノiで遊んだ時に、勝つと1つ右に移動する。このときに勝つ確率はp_i  (= \frac{a_i}{b_i})である。負けると1つ左に移動する(勝率は1 - p_i)。1番目の左側とn番目の右側は出口である。

また、区間 [ i, j ] に対して、次の条件を満たしている時、区間dominateすると呼ぶ:

  • i番目のカジノからスタートする。
  • i番目のカジノでは絶対に負けない。
  • j番目のカジノで勝ち、右に移動して終了する。

次の2種類のクエリを考える:

  • クエリ1 : i,a,bが与えられるので、 p_i\frac{a}{b}にセットする。
  • クエリ2 : l,rが与えられるので、区間 [ l , r ] dominateできる確率を答える。

以上のクエリが合計でq個与えられるので順に処理せよ。

  •  1 \le n \le 100000
  •  1 \le a_i \lt b_i \le 10^9
  •  1 \le q \le 100000
  •  1 \le a \lt b \le 10^9
  •  1 \le l \le r \le n
  • どの状況でも、 p_i \le p_{i+1}が成り立つ。

イデア

区間を管理するために、SegmentTreeを使って高速に処理することを考える。区間のマージをどうするかを考える。

  • X(i,j) : 区間 [ i, j ] dominateできる確率
  • Y(i,j) : 区間 [ i, j ] に対して、jからスタートして、iを超えてしまうこと無く、最終的にはjで勝ち、右に移動できる確率

この上の2つの確率を定義して、区間 [ i, k ] 区間 [ k+1, j ] をマージして区間 [ i, j ] の結果を得ることを考える。x_1 = X(i,k), x_2 = X(k+1,j) , y_1 = Y(i,k), y_2 = Y(k+1,j)とおくと、この4つを使ってX(i,j), Y(i,j)の値を表すことが出来る。

まず、X(i,j)を求める。これは、kk+1の間を何回またぐことになるかで場合分けをすることが出来る。1回またぐのは、ストレートに両区間dominateできれば良いのでx_1 x_2となる。次は、3回またぐパターンだが、これは([i,k]をdominate) → ([k+1,j]でdominate失敗) → ([i,k]でkスタートで耐えてk+1へ) → ([k+1,j]でdominate)という流れになる。この確率は、x_1 (1- x_2) y_1 x_2である。以降またぐ回数が5, 7, 9, ... 回と無限に続き、これは初項x_1 x_2、公比 (1- x_2) y_1の無限等比級数であるから、X(i,j) = \frac{x_1 x_2}{1 - (1- x_2) y_1}である。

次に、Y(i,j)を求める。これも上で考察したことと同様に、kk+1の間を何回またぐことになるか(0, 2, 4, 6, ...回)で場合分けをすることが出来る。0回のときだけは特別で、y_2で、2回以降は初項(1- y_2) y_1 x_2、公比 (1- x_2 ) y_1の無限等比級数であるから、Y(i,j) = y_2 + \frac{(1- y_2) y_1 x_2}{1 - (1- x_2 ) y_1}である。

実装(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

using pd = pair<double, double>;

struct SegTree{
    int n; vector<pd> dat;
    //初期化
    SegTree(int _n){
        n=1;
        while(n<_n) n*=2;
        dat=vector<pd>(2*n-1,{1,0});
    }

    pd merge(pd l, pd r){
        double x1 = l.fi, y1 = l.se;
        double x2 = r.fi, y2 = r.se;

        double X = x1*x2 / (1 - y1*(1-x2));
        double Y = y2 + (1-y2)*y1*x2 / (1 - (1-x2)*y1);
        return {X,Y};
    }

    //k番目(0-indexed)の値をaに変更
    void update(int k, double a){
        k+=n-1;
        dat[k] = {a,a};
        //更新
        while(k>0){
            k=(k-1)/2;
            dat[k]=merge(dat[2*k+1],dat[2*k+2]);
        }
    }
    //内部的に投げられるクエリ
    pd _query(int a, int b, int k, int l, int r){
        if(r<=a || b<=l) return {1,0};

        if(a<=l && r<=b) return dat[k];

        pd vl=_query(a,b,2*k+1,l,(l+r)/2);
        pd vr=_query(a,b,2*k+2,(l+r)/2,r);
        return merge(vl,vr);
    }
    //[a,b)
    pd query(int a, int b){
        return _query(a,b,0,0,n);
    }
};

int main(){
    int n,q;
    scanf(" %d %d", &n, &q);

    SegTree st(n);
    rep(i,n){
        int a,b;
        scanf(" %d %d", &a, &b);
        st.update(i, (double)a/b);
    }

    while(q--){
        int t;
        scanf(" %d", &t);
        if(t==1){
            int i,a,b;
            scanf(" %d %d %d", &i, &a, &b);
            --i;
            st.update(i, (double)a/b);
        }
        else{
            int l,r;
            scanf(" %d %d", &l, &r);
            --l; --r;
            printf("%.10f\n", st.query(l,r+1).fi);
        }
    }

    return 0;
}