http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1490. osu!(乔明达)
时间限制:4.0s   内存限制:256.0MB  
总提交次数:237   AC次数:78   平均分:47.53
将本题分享到:
   
 
问题描述
  osu!是一个基于《押忍!战斗!应援团》《精英节拍特工》《太鼓达人》等各种音乐游戏做成的一款独特的PC版音乐游戏。游戏中,玩家需要根据音乐的节奏,通过鼠标点击或敲击按键合成一首歌曲。
  一张osu!的地图是由若干个“音”排列而成的。在本题中,对于每个音我们只需要考虑成功点击和错过(miss)这两种情况。对于一张osu!地图,玩家的完成情况可以用一个01串表示(0代表miss,1代表成功)。在本题中,使用如下计分规则:将玩家完成一张地图的01串中所有的0删去,则这个串可能会断裂成若干段连续的1。对于一段长度为L的1(L≥1),你的总分会增加L^2+L+1。例如:一张地图有10个音,某玩家完成情况为1011101110,则删除所有0后得到的是“1”“111”和“111”。因此这个玩家的得分为(1+1+1)+(9+3+1)+(9+3+1)=29。
  ACMonster要给Sandytea出一张osu!的地图。在一张图中,不同音对于Sandytea而言难度可能是不同的。我们定义一个音的难度系数为Sandytea成功完成这个音的概率,因此这个难度系数是介于0和1之间的。
  现在ACMonster写下了一个包含N个音的序列,但是他不想直接把这个序列做成地图,而是选择其中的某个片段。设S(X,Y)代表序列上第X个音到第Y个音构成的序列,ACMonster想知道如果把S(X,Y)对应的序列做成地图,Sandytea的期望得分是多少。有时ACMonster会觉得某个音的难度系数不太合理,因此要进行修改。请你想办法处理ACMonster的修改,并回答他提出的问题。
输入格式
  第一行包含两个数N和M,N代表序列中音的个数,M代表询问及修改的总次数。
  第二行至第(N+1)行每行包含一个实数,第i行的实数表示第(i-1)个音的难度系数。
  第(N+2)行至第(N+M+1)行每行包含三个数Type,X和Y。
  如果Type=0,代表ACMonster询问S(X,Y)的期望得分,保证X和Y为整数,1≤X≤Y≤N。
  如果Type=1,代表ACMonster要把第X个音的难度系数修改为Y,保证X为整数,1≤X≤N,0≤Y≤1。
输出格式
  对于输入中所有询问,按照出现的顺序输出相应的答案,四舍五入保留两位小数。
样例输入
2 3
0.5
0.5
0 1 2
1 1 0
0 1 2
样例输出
3.25
1.50
样例说明
  对于第一次询问,00,01,10,11这四种情况出现的概率均为1/4,得分分别为0,3,3,7。因此期望得分为(0+3+3+7)/4=3.25。
  对于第二次询问,00,01这两种情况出现的概率均为1/2,得分分别为0,3。因此期望得分为(0+3)/2=1.50。
数据规模和约定
  20%的数据满足N,M≤5000;
  60%的数据满足N,M≤50000;
  100%的数据满足N,M≤500000。