[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 << 2]; #define lson (o << 1) #define rson (o << 1 | 1) void pushup(int o) { sum[o] = (sum[lson] + sum[rson]) % MOD; } void build(int o, int l, int r) { if (l == r) { sum[o] = a[l]; } else { int mid = (l + r) >> 1; build(lson, l, mid); build(rson, mid + 1, r); pushup(o); } } void change(int o, int l, int r, int q, int v) { if (l == r) { sum[o] = (sum[o] + v) % MOD; return; } int mid = (l + r) >> 1; if (q <= mid) change(lson, l, mid, q, v); else change(rson, mid + 1, r, q, v); pushup(o); } void add_to_interval(int l, int r, int v) { for (int i = l; i <= r; i ++) { change(1, 1, n, i, v); } } ``` 其中 `a` 数组表示每个星星的权值，`sum` 数组表示每个线段树节点的权值，`add_to_interval` 函数表示一次操作。

第一行两个整数 $n,m$，表示序列长度和操作次数。 第二行 $n$ 个整数，表示这个序列。 接下来 $m$ 行，每行为 $1 \ l \ r \ v$，表示区间 $[l,r]$ 的节点加上了 $v$； $2$ ，表示一次询问。

对于每一个 $2$ 操作，输出一个答案。令答案化成最简分数为 $\frac{p}{q}$（保证 $q$ 不是 $998244353$ 的倍数），则输出 $p\cdot q^{-1}\mod 998244353$。

4 3
1 2 3 4
2
1 1 3 1
2

399297760
844668322

对于 $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}$。