P4927 [1007] Mengmei and the Segment Tree

Welcome to the Planetarium. Here, there is beautiful infinite radiance that never disappears at any time. The sky full of stars is waiting for everyone to come.

To study the stars in the Planetarium, Mengmei used a giant projector—Yena—to arrange the stars into a sequence, and then built a segment tree on this star sequence. This is a segment tree that maintains interval sums. The weight of each node is the sum of the weights of all stars in the interval corresponding to that node. Sometimes Mengmei starts a journey in the starry sky from the root node of this segment tree. When she is about to enter a child node, suppose the sums of weights of the intervals corresponding to the left and right subtrees are $sum_l$ and $sum_r$, and the weight of the current node is $sum_{cur}$. Mengmei will enter the left subtree with probability $\frac{sum_l}{sum_{cur}}$, otherwise she enters the right subtree. During the journey, Mengmei adds up the weights of the nodes she passes through. Now she wants you to design an algorithm to compute the expected value of this accumulated weight. Of course, if the stars never change, Mengmei would find it very boring. So she will issue some commands. Each command is: for the stars with indices in $[l,r]$, increase their weights by $v$. However, since all the staff in the museum have left, no one taught Mengmei how to maintain lazy tags on the segment tree, so each of her commands will update all segment tree nodes in real time. To avoid differences in segment tree implementations, here is part of the code Mengmei uses to maintain this problem: ```cpp const int N = 100010, MOD = 998244353; int a[N], sum[N > 1; if (q

The first line contains two integers $n,m$, representing the sequence length and the number of operations. The second line contains $n$ integers, representing this sequence. Next, there are $m$ lines, each being one of the following: $1 \ l \ r \ v$, meaning that all nodes in the interval $[l,r]$ are increased by $v$; $2$, meaning one query.

For each operation $2$, output one answer. Let the answer in lowest terms be $\frac{p}{q}$ (it is guaranteed that $q$ is not a multiple of $998244353$), then output $p\cdot q^{-1}\mod 998244353$.

For $30\%$ of the testdata, it is guaranteed that $1 \leq n,m\leq 100$. For another $20\%$ of the testdata, all operations of type 1 satisfy $l=r$. For $100\%$ of the testdata, it is guaranteed that $1\leq n,m \leq 10^5,1 \leq a_i,v \leq 10^9,1\le l\le r\le n$. The sample answers are actually $\frac{94}{5}$ and $\frac{303}{13}$. Translated by ChatGPT 5