P4927 [1007] 梦美与线段树

欢迎大家光临星象馆 这里有着无论何时永远不会消失 美丽的无穷光辉 满天的星星等候着大家的到来

梦美为了研究星象馆的星星，用巨型投影机——耶拿将星星排成了一个序列，接着梦美将这个星星序列建成了一棵线段树。 这是一棵维护区间和的线段树，每个节点的权值是该节点所对应的区间中，所有星星的权值和。有的时候梦美会从这棵线段树的根节点开始在星空游历。当她要进入子节点的时候，假设左右子树对应区间的权值和分别为 $sum_l$ 和 $sum_r$，当前节点的权值为 $sum_{cur}$ ，梦美会以 $\frac{sum_l}{sum_{cur}}$ 的概率进入左子树，否则进入右子树。 游历的时候，梦美会把她经过的节点的权值累加起来，现在她希望您帮她设计一个算法求出这个权值期望下是多少。 当然，如果星星都是不变的梦美会觉得很没有意思，因此她会发出一些指令，每个指令是，对下标在 $[l,r]$ 的星星，权值加上 $v$ 。不过由于馆里的工作人员全都离开了，因此没有人教梦美在线段树上维护懒标记，所以梦美的每次指令都会实时更新所有的线段树节点。 为了解决线段树写法不一的问题，此处给出梦美维护这个问题时的部分代码： ```cpp const int N = 100010, MOD = 998244353; int a[N], sum[N > 1; if (q

无

无

对于 $30\%$ 的数据，保证 $1 \leq n,m\leq 100$； 对于另外 $20\%$ 的数据，满足所有操作 1 中 $l=r$； 对于 $100\%$ 的数据，保证 $1\leq n,m \leq 10^5,1 \leq a_i,v \leq 10^9,1\le l\le r\le n$。 样例答案实际是 $\frac{94}{5}$ 和 $\frac{303}{13}$。