博客
归档
友链
关于
博客
归档
友链
关于
P2221 [HAOI2012]高速公路
传送门 首先,看到区间修改,区间查询就要想到线段树。 把链上面的操作转化到点上面的的操作,我们像这样编号,点编号为1...n1...n1...n,边编号为1...n−11...n-11...n−1 于是修改和查询都对应到了边[l,r−1][l,r-1][l,r−1] 考虑如何算期望值,下面的分母很简单,就是Cr−l+12C_{r-l+1}^2Cr−l+12,从r−l+1r-l+1r−l...
2019-08-04
阅读全文