作為一名osu!玩家，這道題成功吸引到了我。。。

題意

長(zhǎng)度為n的序列，給出每一個(gè)數(shù)字可能為1的概率ai$a_i$，每個(gè)數(shù)字為0的概率為1?ai$1-a_i$。兩個(gè)操作：修改某個(gè)數(shù)字的概率，詢問一段區(qū)間得分期望，得分計(jì)算方式如下。 將玩家完成一張地圖的01串中所有的0刪去，則這個(gè)串可能會(huì)斷裂成若干段連續(xù)的1。對(duì)于一段長(zhǎng)度為L$L$的1（L≥1）$1（L≥1）$，你的總分會(huì)增加L2+L+1$L^2+L+1$。例如：一張地圖有10個(gè)音，某玩家完成情況為1011101110，則刪除所有0后得到的是“1”“111”和“111”。因此這個(gè)玩家的得分為(1+1+1)+(9+3+1)+(9+3+1)=29。

題解

這是出題人的題解

下面簡(jiǎn)述此題解內(nèi)容。

分值的計(jì)算為∑mi=1(L2i+Li+1)$/sum_{i=1}^{m}(L_i^2+L_i+1)$，m$m$為極大連續(xù)1子段的段數(shù)，leni$len_i$為第i段的長(zhǎng)度。

將其分為三部分分別計(jì)算期望：∑L2i,∑Li$/sum L_i^2, /sum L_i$和∑1$/sum 1$。將這三部分分別記為S2,S1$S_2,S_1$和S0$S_0$。記01串第i$i$位為bi$b_i$，則bi=1$b_i=1$概率為ai$a_i$，bi=0$b_i=0$概率1?ai$1-a_i$。

S1$S_1$的期望 E(S1)=E(∑i=1nbi)=∑i=1nE(bi)=∑i=1nai $$E(S_1) = E(/sum_{i=1}^n b_i) = /sum_{i=1}^n E(b_i) = /sum_{i=1}^n a_i$$ 復(fù)雜度O(n)$O(n)$

S0$S_0$的期望 S0$S_0$的實(shí)際意義是01串中極大1字段的個(gè)數(shù)。關(guān)注每個(gè)這樣子串的起始位置，這樣的位置和子串是一一對(duì)應(yīng)的，只需要統(tǒng)計(jì)有多少位置是子串的起始位置。 考慮第i$i$位，它是起始位置當(dāng)且僅當(dāng)?shù)?nobr>i$i$位是1，第i?1$i-1$位是0。特別地，規(guī)定第0位一定是0，即a0=0$a_0=0$。因此第i$i$位是起始位置的概率為ai(1?ai?1)$a_i(1-a_{i-1})$。 E(S0)=E(∑i=1nai(1?ai?1)) $$E(S_0) = E(/sum_{i=1}^n a_i(1-a_{i-1}))$$ 復(fù)雜度O(n)$O(n)$

E(S2)$E(S_2)$的計(jì)算 由于出現(xiàn)了平方，計(jì)算S2$S_2$的期望并沒有計(jì)算S0$S_0$和S1$S_1$那么簡(jiǎn)單。 定義兩個(gè)數(shù)列 {leni}$/{len_i/}$與{expi}$/{exp_i/}$，leni$len_i$表示{bi}$/{b_i/}$構(gòu)成的01串最長(zhǎng)的全是1的后綴的長(zhǎng)度，expi$exp_i$表示{bi}$/{b_i/}$構(gòu)成的01串S2$S_2$的期望值。len0=0,exp0=0$len_0=0,exp_0=0$。 對(duì)于leni$len_i$，如果bi=1$b_i=1$，則leni=leni?1+1$len_i=len_{i-1}+1$，否則leni=0$len_i=0$，故 leni=ai(leni?1+1)+(1?ai)?0=ai(leni?1+1) $$len_i = a_i(len_{i-1}+1)+(1-a_i)/cdot 0 = a_i(len_{i-1}+1)$$ 對(duì)于expi$exp_i$，如果bi=1$b_i=1$，Δ=(leni?1+1)2?len2i?1=2leni?1+1$/Delta = (len_{i-1}+1)^2-len_{i-1}^2 = 2len_{i-1}+1$，否則Δ=0$/Delta = 0$，故 expi=expi?1+ai(2leni?1+1)+(1?ai)?0=expi?1+ai(2leni?1+1) $$exp_i = exp_{i-1}+a_i(2len_{i-1}+1)+(1-a_i)/cdot 0 = exp_{i-1}+a_i(2len_{i-1}+1)$$ 復(fù)雜度O(n)$O(n)$

用線段樹維護(hù)信息與查詢

維護(hù)S1$S_1$ S1=L.S1+R.S1$S_1 = L.S_1+R.S_1$

維護(hù)S0$S_0$ 若L$L$ai$a_i$值分別為a,b,c,R$R$ai$a_i$值分別為d,e,f. L.S0=a+b(1?a)+c(1?b)$L.S_0 = a+b(1-a)+c(1-b)$ R.S0=d+e(1+d)+f(1?e)$R.S_0 = d+e(1+d)+f(1-e)$ S0=a+b(1?a)+c(1?b)+d(1?c)+e(1?d)+f(1?e)=L.S0+R.S0?cd$S_0 = a+b(1-a)+c(1-b)+d(1-c)+e(1-d)+f(1-e) = L.S_0+R.S_0-cd$ 故記錄區(qū)間左右端點(diǎn)的ai$a_i$值就可以維護(hù)S0$S_0$了。

維護(hù)S2$S_2$ leni=aileni?1+ai$len_i = a_ilen_{i-1}+a_i$ expi=expi?1+2aileni?1+ai$exp_i= exp_{i-1}+2a_ilen_{i-1}+a_i$ 這是一個(gè)線性變換，表示矩陣為 T=???ai0ai2ai1ai001??? $$T = /begin{bmatrix}a_i & 2a_i &0 //0 &1& 0 //a_i& a_i& 1/end{bmatrix}$$ (leni?1,expi?1,1)?T=(leni,expi,1)$(len_{i-1},exp_{i-1},1)/cdot T = (len_i,exp_i,1)$ 所以拿(0,0,1)$(0,0,1)$去乘一整個(gè)區(qū)間的矩陣就能得到(lenk,expk,1)$(len_k,exp_k,1)$，k$k$為區(qū)間長(zhǎng)度，expk$exp_k$為S2$S_2$的答案。 這道題沒有區(qū)間修改不用打標(biāo)記，每個(gè)區(qū)間直接記錄矩陣，由于矩陣乘法的結(jié)合律，可以用線段樹維護(hù)區(qū)間的矩陣乘積。但是直接這么寫常數(shù)太大。 觀察T$T$： ???a0cb1d001??????e0gf1h001???=???ae0ce+gaf?b1cf+d+h001??? $$/begin{bmatrix}a & b & 0//0 & 1 & 0//c & d & 1/end{bmatrix}/begin{bmatrix}e & f & 0//0 & 1 & 0//g & h & 1/end{bmatrix}=/begin{bmatrix}ae & af-b & 0//0 & 1 & 0//ce+g & cf+d+h & 1/end{bmatrix}$$ 可以看到一個(gè)矩陣我們只需記錄四個(gè)值即可，大大減小了常數(shù)。

復(fù)雜度O(n+mlogn)$O(n+m/log n)$

這道題還有個(gè)簡(jiǎn)化版本，在BZOJ4318，給出PO姐的題解

代碼