853 . 種植水稻

Submit out of contest
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Gu2
女兒走在書店，指著一本書大喊「爸爸！這個名字我好像有看過！」我看到他指的名字“八奈見杏菜”不禁笑了笑，指著配偶欄說道「這是媽媽的名字，以後要記清楚喔」

User's AC Ratio

100.0% (15/15)

Submission's AC Ratio

78.8% (26/33)

Tags

ioicamp ioicamp-2025

Description


馬車芽芽芽與小槌正忙著種植水稻

為了實現水稻自給自足，馬車芽芽芽在小鹿社旁開墾了一塊長方形田地，並打算在這塊田地上種水稻。身為一個水稻專家，馬車芽芽芽想要種植的水稻有 109 種那麼多！

為了充份運用這塊田地，馬車芽芽芽先在這塊田地上畫了 N−1 條鉛直線，將田地分成了 N 個區塊，並由左到右為這些區塊編號，依序為 1,2,…,N。為了避免過於壅擠導致水稻生長情況不佳，任意一個區塊至多只會種植一株水稻。

規劃好區塊之後就可以準備種水稻了！一開始每個區塊都沒有種植水稻，接著馬車芽芽芽會進行 Q 個行動，每次會是種植或是採收兩種：

  • 1 l r x，代表一個種植行動：馬車芽芽芽會先移除編號為 l,l+1,…,r 的區塊原先種植的水稻，再將這些區塊都種上一株種類 x 的水稻。
  • 2 l r，代表一個採收行動：馬車芽芽芽覺得編號為 l,l+1,…,r 的區塊上種植的水稻已成熟，會將它們全部採收並交給虎視餡子，讓她用這些稻米製作出美味的飯糰。請注意有可能會有一些區塊沒有種植水稻，那在採收時會跳過那些區塊，而全部有被採收的區塊都會變成沒有種植水稻。

另外，在吃過許多次虎視餡子製作的飯糰後，馬車芽芽芽學習到估計飯糰美味度的方法：首先令 cx 為馬車芽芽芽交給虎視餡子的水稻有幾株的種類為 x，則用這些水稻製作出的飯糰的美味度為 ∑x=1109cx2。特別注意的是若採收行動沒有採收到任何水稻，因為虎視餡子無法製作飯糰，美味度為 0。

現在告訴你馬車芽芽芽 Q 個行動的詳細內容，對於每個採收事件，你能幫幫她計算虎視餡子製作出來的飯糰的美味度是多少嗎？

Input Format

輸入第一行有兩個正整數 N,Q，代表馬車芽芽芽將田地分成的區塊數量與會進行幾個行動。

接下來 Q 行，每行代表一個行動，格式請參考 Description 中的說明。

  • 1≤N≤109
  • 1≤Q≤5×105
  • 1≤l≤r≤N
  • 1≤x≤109
  • 至少有一個採收行動

Output Format

對於每個採收行動輸出一行，該行有一個整數代表該飯糰的美味度。

Sample Input 1

5 8
1 3 5 2
1 2 2 1
2 1 4
1 1 4 3
2 3 5
1 2 5 4
1 4 4 8
2 1 5

Sample Output 1

5
5
11

Sample Input 2

10 8
1 5 5 4
1 7 7 2
2 7 8
1 3 3 6
2 4 9
1 4 4 6
1 6 6 2
2 1 10

Sample Output 2

1
1
5

Sample Input 3

1000000000 3
1 123456789 987654321 864197532
2 48763 56562
2 1 1000000000

Sample Output 3

0
746837376043286089

Hints

以下我們會用一個陣列 a 來表示田地的種植情況，若 ai=0 則代表第 i 個區塊沒有種植水稻，否則代表第 i 個區塊種植了種類 ai 的水稻。則以下為第一筆範例測資的解釋：

  • 一開始 a=[0,0,0,0,0]。
  • 第一個行動後，a=[0,0,2,2,2]。
  • 第二個行動後，a=[0,1,2,2,2]。
  • 第三個行動馬車芽芽芽會採收 1 個種類 1 的水稻 與 2 個種類 2 的水稻，美味度為 5。採收後 a=[0,0,0,0,2]。
  • 第四個行動後，a=[3,3,3,3,2]。
  • 第五個行動馬車芽芽芽會採收 2 個種類 3 的水稻 與 1 個種類 2 的水稻，美味度為 5。採收後 a=[3,3,0,0,0]。
  • 第六個行動後，a=[3,4,4,4,4]。
  • 第七個行動後，a=[3,4,4,8,4]。
  • 第八個行動馬車芽芽芽會採收 1 個種類 3 的水稻、3 個種類 4 的水稻與 1 個種類 8 個水稻，美味度為 11。採收後 a=[0,0,0,0,0]。

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~1, 3~20 N,Q≤5000 5
3 1, 21~40 對於所有種植行動，l=r 30
4 0~70 無額外限制 65

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 524288 65536 1 2 4
1 3000 524288 65536 1 2 3 4
2 3000 524288 65536 1 4
3 3000 524288 65536 2 4
4 3000 524288 65536 2 4
5 3000 524288 65536 2 4
6 3000 524288 65536 2 4
7 3000 524288 65536 2 4
8 3000 524288 65536 2 4
9 3000 524288 65536 2 4
10 3000 524288 65536 2 4
11 3000 524288 65536 2 4
12 3000 524288 65536 2 4
13 3000 524288 65536 2 4
14 3000 524288 65536 2 4
15 3000 524288 65536 2 4
16 3000 524288 65536 2 4
17 3000 524288 65536 2 4
18 3000 524288 65536 2 4
19 3000 524288 65536 2 4
20 3000 524288 65536 2 4
21 3000 524288 65536 3 4
22 3000 524288 65536 3 4
23 3000 524288 65536 3 4
24 3000 524288 65536 3 4
25 3000 524288 65536 3 4
26 3000 524288 65536 3 4
27 3000 524288 65536 3 4
28 3000 524288 65536 3 4
29 3000 524288 65536 3 4
30 3000 524288 65536 3 4
31 3000 524288 65536 3 4
32 3000 524288 65536 3 4
33 3000 524288 65536 3 4
34 3000 524288 65536 3 4
35 3000 524288 65536 3 4
36 3000 524288 65536 3 4
37 3000 524288 65536 3 4
38 3000 524288 65536 3 4
39 3000 524288 65536 3 4
40 3000 524288 65536 3 4
41 3000 524288 65536 4
42 3000 524288 65536 4
43 3000 524288 65536 4
44 3000 524288 65536 4
45 3000 524288 65536 4
46 3000 524288 65536 4
47 3000 524288 65536 4
48 3000 524288 65536 4
49 3000 524288 65536 4
50 3000 524288 65536 4
51 3000 524288 65536 4
52 3000 524288 65536 4
53 3000 524288 65536 4
54 3000 524288 65536 4
55 3000 524288 65536 4
56 3000 524288 65536 4
57 3000 524288 65536 4
58 3000 524288 65536 4
59 3000 524288 65536 4
60 3000 524288 65536 4
61 3000 524288 65536 4
62 3000 524288 65536 4
63 3000 524288 65536 4
64 3000 524288 65536 4
65 3000 524288 65536 4
66 3000 524288 65536 4
67 3000 524288 65536 4
68 3000 524288 65536 4
69 3000 524288 65536 4
70 3000 524288 65536 4
Submit out of contest
Back to Top