[TsinsenA1490] osu!（乔明达）

作为一名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姐的题解

代码