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

題意

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

題解

這是出題人的題解

下面簡述此題解內容。

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

將其分為三部分分別計算期望：∑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$$ 復雜度O(n)$O(n)$

S0$S_0$的期望 S0$S_0$的實際意義是01串中極大1字段的個數。關注每個這樣子串的起始位置，這樣的位置和子串是一一對應的，只需要統計有多少位置是子串的起始位置。 考慮第i$i$位，它是起始位置當且僅當第i$i$位是1，第i?1$i-1$位是0。特別地，規定第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}))$$ 復雜度O(n)$O(n)$

E(S2)$E(S_2)$的計算 由于出現了平方，計算S2$S_2$的期望并沒有計算S0$S_0$和S1$S_1$那么簡單。 定義兩個數列 {leni}$/{len_i/}$與{expi}$/{exp_i/}$，leni$len_i$表示{bi}$/{b_i/}$構成的01串最長的全是1的后綴的長度，expi$exp_i$表示{bi}$/{b_i/}$構成的01串S2$S_2$的期望值。len0=0,exp0=0$len_0=0,exp_0=0$。 對于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)$$ 對于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)$$ 復雜度O(n)$O(n)$

用線段樹維護信息與查詢

維護S1$S_1$ S1=L.S1+R.S1$S_1 = L.S_1+R.S_1$

維護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$ 故記錄區間左右端點的ai$a_i$值就可以維護S0$S_0$了。

維護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$ 這是一個線性變換，表示矩陣為 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)$去乘一整個區間的矩陣就能得到(lenk,expk,1)$(len_k,exp_k,1)$，k$k$為區間長度，expk$exp_k$為S2$S_2$的答案。 這道題沒有區間修改不用打標記，每個區間直接記錄矩陣，由于矩陣乘法的結合律，可以用線段樹維護區間的矩陣乘積。但是直接這么寫常數太大。 觀察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}$$ 可以看到一個矩陣我們只需記錄四個值即可，大大減小了常數。

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

這道題還有個簡化版本，在BZOJ4318，給出PO姐的題解

代碼