P4247 [Tsinghua Training 2012] Sequence Operations

There is a sequence of length $n$ with three operations: 1. `I a b c` means adding $c$ to all elements in the interval $[a,b]$. 2. `R a b` means turning all elements in the interval $[a,b]$ into their opposites (negating them). 3. `Q a b c` means querying the value of the sum of products over all ways to choose $c$ numbers from the interval $[a,b]$, taken $\mod 19940417$.

The first line contains two integers $n, q$, denoting the sequence length and the number of operations. The second line contains $n$ integers, representing the sequence. Each of the next $q$ lines contains one operation, either `I a b c`, `R a b`, or `Q a b c`, with meanings as described above.

For each query, output the value of the sum of products over all ways to choose $c$ numbers from the specified interval, taken $\mod 19940417$.

Sample explanation: After the first operation, the sequence becomes `1 3 4 4 5`. The result of the first query is $3 \times 4 + 3 \times 4 + 4 \times 4 = 40$. After the `R` operation, it becomes `-1 -3 -4 -4 -5`. After the `I` operation, it becomes `-2 -4 -5 -4 -5`. The result of the second query is $(-2)+(-4)+(-5)+(-4)+(-5)=-20$. Constraints: For $100\%$ of the testdata, $n \leq 50000, q \leq 50000$. The absolute value of each element in the initial sequence is $\leq 10^9$. It is guaranteed that $[a,b]$ is a valid interval. In operation `I`, $|c| \leq 10^9$. In operation `Q`, $1 \leq c \leq \min(b-a+1,20)$. Translated by ChatGPT 5