#P6707. Sequence Manipulation Queries
Sequence Manipulation Queries
Sequence Manipulation Queries
Given a sequence \(f\), perform a series of operations on it. The operations are defined as follows:
| Query Type | Description |
|---|---|
1 A B X |
Assign \( f_i = X \) for all indices \( A \le i \le B \). |
2 A B X |
Add \( (i-A+1) \times X \) to \( f_i \) for all indices \( A \le i \le B \). |
3 C X |
Insert \( X \) at position \( C \). In other words, for all \( i \) with \( C \le i \le n \), the element \( f_i \) is shifted to \( f_{i+1} \), and \( f_C \) is set to \( X \). |
4 A B |
Output the sum \( \sum_{i=A}^{B} f_i \). |
The sequence is 1-indexed. Initially, you are given \( n \) integers forming the sequence \( f \) followed by \( q \) queries. For each query of type 4, output the corresponding sum in a new line.
inputFormat
The first line contains two integers \( n \) and \( q \): the length of the sequence and the number of queries.
The second line contains \( n \) integers representing the initial sequence \( f \).
The next \( q \) lines each contain a query. A query is in one of the following formats:
1 A B X2 A B X3 C X4 A B
outputFormat
For every query of type 4, output a single line containing an integer: the sum \( \sum_{i=A}^{B} f_i \).
sample
5 7
1 2 3 4 5
4 1 5
1 2 4 10
4 2 4
2 3 5 2
4 1 5
3 3 7
4 3 615
30
48
44