P2221 [HAOI2012] Highway

The Y901 Expressway is an important transportation link. Both the initial construction investment and the maintenance costs during operation are high, so the government has set up many toll stations on this expressway.

The Y901 Expressway is an east–west chain consisting of $n-1$ road segments and $n$ toll stations. From west to east, we number the stations $1$ to $n$. Traveling from station $i$ to $i+1$ (or from $i+1$ to $i$) costs $v_i$. When the expressway was first built, all segments were free, i.e., all $v_i = 0$. The authorities will, from time to time, adjust the toll standards for consecutive segments, increasing or decreasing them according to policy. A bored student, "Xiao A" (pinyin: Xiao A), likes to ponder quirky questions. While driving on this expressway, he wondered: for given $l, r$, choose two distinct stations $a$ and $b$ uniformly at random from stations $l$ through $r$. What is the expected cost to travel from $a$ to $b$?

The first line contains two integers $n$ and $m$, the number of toll stations and the total number of updates and queries. Each of the next $m$ lines describes an update or a query and begins with a character $op$. - If $op$ is `C`, then there follow three integers $l, r, v$, meaning: increase by $v$ the toll on every road segment between the $l$-th and the $r$-th stations (i.e., all segments with indices $i$ where $l \le i < r$). - If $op$ is `Q`, then there follow two integers $l, r$. For the given $l, r$, answer Xiao A’s question.

For each query, output a single line containing the answer as a reduced fraction. If the answer is an integer $a$, output `a/1`.

Constraints There are $10$ test points. The scale of each test point is as follows. | Test Point | $n=$ | $m=$ | | :--------: | :--: | :--: | | 1 | $10$ | $10$ | | 2 | $100$ | $100$ | | 3 | $1000$ | $1000$ | | 4 | $10000$ | $10000$ | | 5 | $50000$ | $50000$ | | 6 | $60000$ | $60000$ | | 7 | $70000$ | $70000$ | | 8 | $80000$ | $80000$ | | 9 | $90000$ | $90000$ | | 10 | $100000$ | $100000$ | For all test points, it is guaranteed that $1 \le n, m \le 10^5$, $op \in \{\texttt{C}, \texttt{Q}\}$, $1 \le l \le r \le n$, $-10^4 \le v \le 10^4$, and at any time $0 \le v_i \le 10^4$. Translated by ChatGPT 5