TopCoder

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

User's AC Ratio

100.0% (14/14)

Submission's AC Ratio

78.1% (25/32)

Tags

Description


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

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

為了充份運用這塊田地,馬車芽芽芽先在這塊田地上畫了 N1 條鉛直線,將田地分成了 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 中的說明。

  • 1N109
  • 1Q5×105
  • 1lrN
  • 1x109
  • 至少有一個採收行動

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,Q5000 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