f986: Polynomial Queries
Tags :
Accepted rate : 5人/12人 ( 42% ) [非即時]

Content

Your task is to maintain an array of $\color{black}{n}\$ values and efficiently process the following types of queries:

1. Increase the first value in range $\color{black}{[\ a,b\ ]}\$ by $\color{black}{1}\$ , the second value by $\color{black}{2}\$ , the third value by $\color{black}{3}\$ , and so on.
2. Calculate the sum of values in range $\color{black}{[\ a,b\ ]}\$ .

1. 將範圍在 $\color{black}{[\ a,b\ ]}\$ 間的元素，第一個元素加 $\color{black}{1}\$，第二個元素加 $\color{black}{2}\$，第三個元素加 $\color{black}{3}\$，依此類推。
2. 計算在區間 $\color{black}{[\ a,b\ ]}\$ 的元素總和。

Input

The first input line has two integers $\color{black}{n}\$ and $\color{black}{q}\$ : the size of the array and the number of queries.

The next line has $\color{black}{n}\$ values $\color{black}{t_1,t_2,...,t_n}\$ : the initial contents of the array.

Finally, there are $\color{black}{q}\$ lines describing the queries. The format of each line is either " $\color{black}{1\ a\ b}\$ " or " $\color{black}{2\ a\ b}\$ ".

• $\color{black}{1≤n,q≤2\times 10^5}\$
• $\color{black}{1≤t_i≤10^6}\$
• $\color{black}{1≤a≤b≤n}\$
Output

Print the answer to each sum query.

Sample Input #1
5 3
4 2 3 1 7
2 1 5
1 1 5
2 1 5
Sample Output #1
17
32

Hint ：

$\color{black}{100\%：無特別限制}\$

Tags:

[管理者：
(Caido)
]

 ID User Problem Subject Hit Post Date 沒有發現任何「解題報告」