180 . 白雪飄飄

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

60.0% (6/10)

Tags

ioicamp ioicamp-2022

Description

在一個寒冷的冬天，北國開始飄雪了！北國的房屋是一整排直線排列的，並且由前至後編號 $1\sim N$。因此在每波雪情中，總是可以被視為一段連續的房屋 $u, u+1, \dots, v$ 積了 $w$ 公分的雪，然而這樣的積雪卻會對房屋造成損害。根據專家估計，$x$ 公分的積雪會對房屋造成 $x^ 2$ 單位的損害。為了防止嚴重的災情，時不時會有長官來視察一段編號 $u, u+1, \dots, v$ 的房子，並計算這些房屋總損害值。

請你寫一個程式維護這些降雪事件，並在長官前來關切時告訴他所求區間房屋總損害值。在本題中，我們假設積雪不會隨時間融化。

Input Format

輸入第一行是兩個整數 $N, Q$，分別代表房屋數量和事件數量。

第二行是 $N$ 個整數 $a_1, a_2, \dots, a_N$，代表每個房屋的初始積雪是多少公分。

接著有 $Q$ 行事件，每行為以下兩種格式之一：

  • $1\ u\ v\ w$：表示一個下雪事件，在第 $u$ 到 $v$ 號房降下厚度 $w$ 公分的雪。
  • $2\ u\ v$：表示一個長官關切事件，請你回答第 $u$ 到 $v$ 號房的房屋損壞程度。

資料滿足：

  • $1\le N, Q\le 2\times 10^ 5$
  • $1\le a_i\le 10^ 9$
  • $1\le u < v\le N$
  • $1\le w\le 10^ 9$

Output Format

對於每次第二種事件，輸出一行一個整數，表示房屋的總損壞程度。

答案可能很大，請輸出 $\text{mod } 10^ 9+7$ 的結果。

Sample Input 1

3 3
1 2 3
2 1 3
1 1 2 1
2 1 2

Sample Output 1

14
13

Sample Input 2

5 5
0 5 3 0 7
1 1 3 5
2 3 5
1 2 3 4
1 3 5 1
2 1 2

Sample Output 2

113
221

Hints

Problem Source

IOICamp 2022 Day4 pC

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~15 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 262144 65536 1 2
1 3000 262144 65536 1 2
2 3000 262144 65536 2
3 3000 262144 65536 2
4 3000 262144 65536 2
5 3000 262144 65536 2
6 3000 262144 65536 2
7 3000 262144 65536 2
8 3000 262144 65536 2
9 3000 262144 65536 2
10 3000 262144 65536 2
11 3000 262144 65536 2
12 3000 262144 65536 2
13 3000 262144 65536 2
14 3000 262144 65536 2
15 3000 262144 65536 2
Submit
Back to Top