853 . 種植水稻
TopCoder
Tags
Description
馬車芽芽芽與小槌正忙著種植水稻
為了實現水稻自給自足，馬車芽芽芽在小鹿社旁開墾了一塊長方形田地，並打算在這塊田地上種水稻。身為一個水稻專家，馬車芽芽芽想要種植的水稻有 $10^ 9$ 種那麼多！
為了充份運用這塊田地，馬車芽芽芽先在這塊田地上畫了 $N - 1$ 條鉛直線，將田地分成了 $N$ 個區塊，並由左到右為這些區塊編號，依序為 $1, 2, \ldots, N$。為了避免過於壅擠導致水稻生長情況不佳，任意一個區塊至多只會種植一株水稻。
規劃好區塊之後就可以準備種水稻了！一開始每個區塊都沒有種植水稻，接著馬車芽芽芽會進行 $Q$ 個行動，每次會是種植或是採收兩種：
- $1 \ l \ r \ x$，代表一個種植行動：馬車芽芽芽會先移除編號為 $l, l + 1, \ldots, r$ 的區塊原先種植的水稻，再將這些區塊都種上一株種類 $x$ 的水稻。
- $2 \ l \ r$，代表一個採收行動：馬車芽芽芽覺得編號為 $l, l + 1, \ldots, r$ 的區塊上種植的水稻已成熟，會將它們全部採收並交給虎視餡子，讓她用這些稻米製作出美味的飯糰。請注意有可能會有一些區塊沒有種植水稻，那在採收時會跳過那些區塊，而全部有被採收的區塊都會變成沒有種植水稻。
另外，在吃過許多次虎視餡子製作的飯糰後，馬車芽芽芽學習到估計飯糰美味度的方法：首先令 $c_x$ 為馬車芽芽芽交給虎視餡子的水稻有幾株的種類為 $x$，則用這些水稻製作出的飯糰的美味度為 $\sum\limits_{x = 1}^ {10^ 9}c_x^ 2$。特別注意的是若採收行動沒有採收到任何水稻，因為虎視餡子無法製作飯糰，美味度為 $0$。
現在告訴你馬車芽芽芽 $Q$ 個行動的詳細內容，對於每個採收事件，你能幫幫她計算虎視餡子製作出來的飯糰的美味度是多少嗎？
Input Format
輸入第一行有兩個正整數 $N, Q$，代表馬車芽芽芽將田地分成的區塊數量與會進行幾個行動。
接下來 $Q$ 行，每行代表一個行動，格式請參考 Description 中的說明。
- $1 \leq N \leq 10^ 9$
- $1 \leq Q \leq 5 \times 10^ 5$
- $1 \leq l \leq r \leq N$
- $1 \leq x \leq 10^ 9$
- 至少有一個採收行動
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
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
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
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
1
5
Sample Input 3
1000000000 3
1 123456789 987654321 864197532
2 48763 56562
2 1 1000000000
1 123456789 987654321 864197532
2 48763 56562
2 1 1000000000
Sample Output 3
0
746837376043286089
746837376043286089
Hints
以下我們會用一個陣列 $a$ 來表示田地的種植情況，若 $a_i = 0$ 則代表第 $i$ 個區塊沒有種植水稻，否則代表第 $i$ 個區塊種植了種類 $a_i$ 的水稻。則以下為第一筆範例測資的解釋：
- 一開始 $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 \leq 5000$ | 5 |
| 3 | 1, 21~40 | 對於所有種植行動，$l = r$ | 30 |
| 4 | 0~70 | 無額外限制 | 65 |