Background

CTT2021 D2T1

Problem Description

Xiao D is a master of data structures. He especially likes studying data structures with simple forms. Today he came up with the following problem.

You have a sequence $a$ of length $n$. You need to perform $q$ modifications or queries:

1. Given $v$, change every $a_i$ to $\min(a_i, v)$.
2. Change every $a_i$ to $a_i + i$.
3. Given $l, r$, query $\sum_{i=l}^r a_i$.

As a top-level data structure master, Xiao D solved this problem easily. Now he wants to test you, who are about to take part in IOI2022. He believes you can also solve it easily.

Input Format

The first line contains two positive integers $n, q$, representing the length of the sequence and the number of modifications/queries.

The next line contains $n$ integers $a_i$, representing the initial sequence $a$.

The next $q$ lines each start with a positive integer $op_i$, indicating the type of the $i$-th modification/query.

• If $op_i = 1$, it is followed by an integer $v_i$, meaning perform modification 1 once.
• If $op_i = 2$, it means perform modification 2 once.
• If $op_i = 3$, it is followed by two positive integers $l_i, r_i$, meaning perform query 3 once.

Output Format

Output several lines, each containing one integer as an answer.

15 15
6 14 14 6 3 6 4 13 10 3 12 5 11 9 6
1 9
1 2
2
2
2
1 11
3 4 6
2
1 6
2
1 9
1 11
1 11
3 4 4
3 2 13

33
9
107

Hint

Constraints: $1 \leq n, q \leq 2 \times 10^5$, $0 \leq a_i, v_i \leq 10^{12}$.

Property A: $a_i, v_i$ are generated uniformly at random in $[0, 10^{12}]$, $op_i$ is generated uniformly at random in $[1, 3]$, and $[l_i, r_i]$ is generated uniformly at random among all valid intervals.

Translated by ChatGPT 5