P3772 [CTSC2017] 游戲

sol

首先，由期望的線性性，把貢獻拆到單點上，對每一場計算其勝利的概率即可。

首先已知的局可以不管，未知的局，顯然只與其兩側最近的已知局有關。后面運用的一些概率表達在題面最下面有提到，就不額外解釋了。

記 \(L,R\) 分別為兩側已知局與已知狀態相同的事件，\(X\) 表示當前局獲勝的概率，那么我們就是要求：\(p(X\mid LR)\)。這個游戲是一個 Markov 過程，每個狀態只依賴于上一個狀態轉移，則可以推出下式：

感性理解這個式子的話也是簡單的，就是 \(L\) 必然發生時，\(XR\) 同時發生的概率比上 \(R\) 發生的概率，也就是要求的 \(X\) 發生的概率。

這個東西已經可以求了，考慮優化，上面說到每個局只與相鄰兩個已知局有關，那么考慮對一個未知局連續段統一計算。

分母是易求的，只需要順序遞推一下即可，有轉移方程：

狀態設計顯然。考慮分子，也就是欽定 \(x\) 處必勝，并對所有情況求和。這個直接狀態設計的話有點復雜，這里就略去了，因為后面介紹的轉移方式很方便。

那么考慮 set 維護所有已知點，更新時動態計算變化的連續段答案，利用矩陣把轉移掛到線段樹上區間求和即可。

設計狀態矩陣，兩個事件分別表示當前贏和輸：

\(f\) 的轉移矩陣設計直接照搬即可：

考慮分子，欽定一個點必勝是簡單的，把那個位置的轉移矩陣改成下面這個樣子即可：

在線段樹上維護欽定一個點的所有情況求和是簡單的，每個節點額外維護一個矩陣信息 \(G\) 表示區間已有一個欽定點的狀態，記當前節點為 \(x\)，兩個子兒子分別為 \(ls\) 和 \(rs\)，區間轉移矩陣信息記作 \(F\)，有轉移：

意義顯然。

具體實現細節的話，可以考慮欽定 \(0,n+1\) 必勝來方便代碼，其余的就參照代碼實現吧。

code

const int N=2e5+5;

struct Mat{
    flt dat[2][2];
    Mat(){rep(i,0,1)rep(j,0,1)dat[i][j]=0;}
    Mat(flt a,flt b,flt c,flt d){dat[0][0]=a,dat[0][1]=b,dat[1][0]=c,dat[1][1]=d;}
    inline flt* operator[](int k){return dat[k];}
    friend inline Mat operator*(Mat a,Mat b){
        Mat c;
        rep(i,0,1)rep(j,0,1)rep(k,0,1)c[i][j]+=a[i][k]*b[k][j];
        return c;
    }
    friend inline Mat operator+(Mat a,Mat b){
        Mat c;
        rep(i,0,1)rep(j,0,1)c[i][j]=a[i][j]+b[i][j];
        return c;
    }
};

int n,m;
flt p[N],q[N];
set<int> st;
bool w[N];
int ck;flt cn;

Mat M[N],dat[N<<2],pro[N<<2];
void build(int x=1,int l=1,int r=n){
    if(l==r){
        dat[x]=M[l]={p[l],1-p[l],q[l],1-q[l]};
        pro[x]={p[l],0,q[l],0};
        return;
    }
    int m=l+r>>1;
    build(x<<1,l,m);
    build(x<<1|1,m+1,r);
    dat[x]=dat[x<<1]*dat[x<<1|1];
    pro[x]=pro[x<<1]*dat[x<<1|1]+dat[x<<1]*pro[x<<1|1];
}
pair<Mat,Mat> query(int lq,int rq,int x=1,int l=1,int r=n){
    if(lq<=l&&r<=rq)return {dat[x],pro[x]};
    int m=l+r>>1;
    if(rq<=m)return query(lq,rq,x<<1,l,m);
    if(m<lq)return query(lq,rq,x<<1|1,m+1,r);
    auto resl=query(lq,rq,x<<1,l,m),resr=query(lq,rq,x<<1|1,m+1,r);
    return {resl.fir*resr.fir,resl.sec*resr.fir+resl.fir*resr.sec};
}
inline flt calc(int l,int r){
    if(l==r-1)return 0;
    Mat m;m[0][w[l]^1]=1;
    auto res=query(l+1,r-1);
    Mat sum=m*res.fir*M[r],prd=m*res.sec*M[r];
    return prd[0][w[r]^1]/sum[0][w[r]^1];
}

inline void Main(){
    char type;cin>>n>>m>>type;
    cin>>p[1];rep(i,2,n)cin>>p[i]>>q[i];
    st.insert(0),st.insert(n+1);
    build();M[n+1]={1,0,1,0};w[0]=w[n+1]=1;
    cn=calc(0,n+1);
    rep(i,1,m){
        string op;cin>>op;
        if(op=="add"){
            int x,c;cin>>x>>c;
            if(w[x]=c)++ck;
            auto it=st.lower_bound(x);
            int r=*it;int l=*--it;
            cn+=calc(l,x)+calc(x,r)-calc(l,r);
            st.insert(x);
        }else{
            int x;cin>>x;
            if(w[x])--ck;
            auto it=st.upper_bound(x);
            int r=*it;int l=*----it;
            cn+=calc(l,r)-calc(l,x)-calc(x,r);
            st.erase(x);
        }
        put(ck+cn);
    }
}