作为一名osu!玩家,这道题成功吸引到了我。。。
题意
长度为n的序列,给出每一个数字可能为1的概率ai,每个数字为0的概率为1−ai。两个操作:修改某个数字的概率,询问一段区间得分期望,得分计算方式如下。 将玩家完成一张地图的01串中所有的0删去,则这个串可能会断裂成若干段连续的1。对于一段长度为L的1(L≥1),你的总分会增加L2+L+1。例如:一张地图有10个音,某玩家完成情况为1011101110
,则删除所有0后得到的是“1”“111”和“111”
。因此这个玩家的得分为(1+1+1)+(9+3+1)+(9+3+1)=29
。
题解
这是出题人的题解
下面简述此题解内容。
分值的计算为∑mi=1(L2i+Li+1),m为极大连续1子段的段数,leni为第i段的长度。
将其分为三部分分别计算期望:∑L2i,∑Li和∑1。将这三部分分别记为S2,S1和S0。记01串第i位为bi,则bi=1概率为ai,bi=0概率1−ai。
S1的期望 E(S1)=E(∑i=1nbi)=∑i=1nE(bi)=∑i=1nai 复杂度O(n)
S0的期望 S0的实际意义是01串中极大1字段的个数。关注每个这样子串的起始位置,这样的位置和子串是一一对应的,只需要统计有多少位置是子串的起始位置。 考虑第i位,它是起始位置当且仅当第i位是1,第i−1位是0。特别地,规定第0位一定是0,即a0=0。因此第i位是起始位置的概率为ai(1−ai−1)。 E(S0)=E(∑i=1nai(1−ai−1)) 复杂度O(n)
E(S2)的计算 由于出现了平方,计算S2的期望并没有计算S0和S1那么简单。 定义两个数列 {leni}与{expi},leni表示{bi}构成的01串最长的全是1的后缀的长度,expi表示{bi}构成的01串S2的期望值。len0=0,exp0=0。 对于leni,如果bi=1,则leni=leni−1+1,否则leni=0,故 leni=ai(leni−1+1)+(1−ai)⋅0=ai(leni−1+1) 对于expi,如果bi=1,Δ=(leni−1+1)2−len2i−1=2leni−1+1,否则Δ=0,故 expi=expi−1+ai(2leni−1+1)+(1−ai)⋅0=expi−1+ai(2leni−1+1) 复杂度O(n)
用线段树维护信息与查询
维护S1 S1=L.S1+R.S1
维护S0 若Lai值分别为a,b,c,Rai值分别为d,e,f. L.S0=a+b(1−a)+c(1−b) R.S0=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 故记录区间左右端点的ai值就可以维护S0了。
维护S2 leni=aileni−1+ai expi=expi−1+2aileni−1+ai 这是一个线性变换,表示矩阵为 T=⎡⎣⎢ai0ai2ai1ai001⎤⎦⎥ (leni−1,expi−1,1)⋅T=(leni,expi,1) 所以拿(0,0,1)去乘一整个区间的矩阵就能得到(lenk,expk,1),k为区间长度,expk为S2的答案。 这道题没有区间修改不用打标记,每个区间直接记录矩阵,由于矩阵乘法的结合律,可以用线段树维护区间的矩阵乘积。但是直接这么写常数太大。 观察T: ⎡⎣⎢a0cb1d001⎤⎦⎥⎡⎣⎢e0gf1h001⎤⎦⎥=⎡⎣⎢ae0ce+gaf−b1cf+d+h001⎤⎦⎥ 可以看到一个矩阵我们只需记录四个值即可,大大减小了常数。
复杂度O(n+mlogn)
这道题还有个简化版本,在BZOJ4318,给出PO姐的题解
代码
/// by ztx/// blog.csdn.net/hzoi_ztx#define Rep(i,l,r) for(i=(l);i<=(r);i++)#define rep(i,l,r) for(i=(l);i< (r);i++)#define Rev(i,r,l) for(i=(r);i>=(l);i--)#define rev(i,r,l) for(i=(r);i> (l);i--)#define Each(i,v) for(i=v.begin();i!=v.end();i++)typedef long long ll ;typedef double lf ;int CH , NEG ;template <typename TP>inline void read(TP& ret) { ret = NEG = 0 ; while (CH=getchar() , CH<'!') ; if (CH == '-') NEG = true , CH = getchar() ; while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ; if (NEG) ret = -ret ;}#define kN 500010LL#define kT 2000010LL#define M ((L+R)/2)#define l(o) (o<<1)#define r(o) (o<<1|1)#define left l(o),L,M#define right r(o),M+1,Rstruct mat { lf x[4]; };inline mat Mul(const mat&a,const mat&b) { return (mat){a.x[0]*b.x[0],a.x[0]*b.x[1]+a.x[1],a.x[2]*b.x[0]+b.x[2],a.x[2]*b.x[1]+a.x[3]+b.x[3]};}inline void One(mat&a) { a.x[0] = 1.0, a.x[1] = a.x[2] = a.x[3] = 0;}inline lf Ans(const mat&a) { return a.x[3];// (0,0,1) * (a b 0) = (c,d,1)// (0 1 0) ^// (c d 1)}int n, ql, qr;lf a[kN], qw, qa0, qa1, qra;mat qa2;lf s0[kT], s1[kT], la[kT], ra[kT];mat t[kT];void update(int o) { la[o] = la[l(o)], ra[o] = ra[r(o)]; s0[o] = s0[l(o)]+s0[r(o)]-ra[l(o)]*la[r(o)]; s1[o] = s1[l(o)]+s1[r(o)]; t[o] = Mul(t[l(o)],t[r(o)]);}void Build(int o=1, int L=1, int R=n) { if (L == R) { t[o].x[0] = t[o].x[2] = t[o].x[3] = a[L], t[o].x[1] = a[L]*2; la[o] = ra[o] = s0[o] = s1[o] = a[L]; return ; } Build(left), Build(right); update(o);}void Modify(int o=1, int L=1, int R=n) { if (L == R) { a[L] = qw; t[o].x[0] = t[o].x[2] = t[o].x[3] = qw, t[o].x[1] = qw*2; la[o] = ra[o] = s0[o] = s1[o] = qw; return ; } if (ql <= M) Modify(left); else Modify(right); update(o);}void Query(int o=1, int L=1, int R=n) { if (ql<=L && R<=qr) { qa0 += s0[o]-qra*la[o], qra = ra[o]; qa1 += s1[o]; qa2 = Mul(qa2,t[o]); return ; } if (ql <= M) Query(left); if (qr > M) Query(right);}#undef r#define r(x) read(x)int main() { int m, i, ope; r(n), r(m); Rep (i,1,n) scanf("%lf", &a[i]); Build(); while (m --> 0) { r(ope); if (ope) r(ql), scanf("%lf", &qw), Modify(); else r(ql), r(qr), qa0=qa1=qra=0, One(qa2), Query(), PRintf("%.2f/n", qa0+qa1+Ans(qa2)); } END: getchar(), getchar(); return 0;}