f986: Polynomial Queries
Tags : BIT 線段樹
Accepted rate : 5人/12人 ( 42% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-10-01 17:32

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\ ]}\ $ .

你的任務是要對大小為 $\color{black}{n}\ $ 的陣列做下列的事:

  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}{n}\ $ 和 $\color{black}{q}\ $ 代表陣列的大小和要詢問的次數。

下一行有 $\color{black}{n}\ $ 個數字 $\color{black}{t_1,t_2,...,t_n}\ $ 代表陣列的初始值。

最後有 $\color{black}{q}\ $ 行詢問。格式為 " $\color{black}{1\ a\ b}\ $ " 或 " $\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
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (8%): 1.0s , <1K
公開 測資點#1 (12%): 1.0s , <1M
公開 測資點#2 (40%): 3.0s , <10M
公開 測資點#3 (40%): 3.0s , <10M
Hint :

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

Tags:
BIT 線段樹
出處:
CSES1736 [管理者:
becaido (Caido)
]


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