18 . A 子的飲料店
TopCoder
Tags
Description
A 子最近在工作時陷入洩密風波，不幸被公司解僱了，更因為種種原因與丈夫離婚，為了維持生計，A 子決定開一間飲料店販售可可、米漿、美祿等等受歡迎的飲料。特別的是，為了增添飲料的風味，A 子的飲料店不提供單一口味的飲料，而是供應恰兩種飲料的組合。例如，雖然可可和美祿都是巧克力飲品，兩者混和卻能夠將不同口感融合、進一步帶出飲料的層次感。A 子的飲料店還養了一隻可愛的貓咪，雖然牠看不見，但客人還是很喜歡跟牠玩，飲料店的人氣也蒸蒸日上。
作為一名馬夫的你，平時在駕駛馬車的空閒時間總喜歡來幾杯飲料犒賞自己；這天，你發現了 A 子新開的飲料店，能一邊聽音樂、一邊喝著冰冰涼涼濃郁順口的米漿、一邊走在回家的路上最幸福了 ٩(´ᗜ`*)୨
「老闆，來一杯米漿！」
「你不知道，好多人最喜歡喝米漿，但是米漿已經賣完一陣子了。而且我們飲料店比較特別，你要選兩種飲料搭配著喝，要不要換個口味？」
「原來如此，那我要可可加美祿。」
「抱歉啊，今天客人很多，可可很早就賣完了，不久前美祿也沒了。最近美祿被廠商那邊查出來有什麼違規的，以後可能都沒辦法再進貨了。」
三番兩次點飲料失敗讓你很失望。你生氣了，決定連買飲料都要內卷，每天早上六點起床把 A 子飲料店的飲料都掃一輪。具體來說，你把 A 子飲料店的所有 $N$ 種飲料都標上一個編號，第 $i$ 種飲料有好喝度 $a_i$。每天早上，你可能會根據心情選一個區間 $[l, r]$，對於所有編號是 $i, j (l \le i < j \le r)$ 的兩種飲料的組合都買一杯來喝，獲得的滿足度會是每一杯飲料的 $a_i \cdot a_j$ 的總和。在這期間也有可能遇到某種飲料售罄的情況，A 子會進貨一種新的飲料取代賣完的飲料，讓編號 $p$ 的飲料好喝度更新為 $x$。
在接下來的一段時間，你手上紀錄了許多事件，這些事件可能是你早上去買了哪些飲料、或是哪一種飲料賣光了要換成新飲料，但亂喝飲料的下場就是你大病一場忘光你以前都喝過什麼黑暗料理。你能從這些紀錄還原出你每次喝飲料都獲得了多少滿足度嗎？
Input Format
輸入第一行是一個整數 $N$，代表 A 子的飲料店有賣幾種飲料。
第二行是 $N$ 個整數 $a_1, a_2, \dots, a_N$，代表每一種飲料的好喝度。
第三行是一個整數 $Q$，代表接下來的事件數量。
接下來 $Q$ 行，每行三個整數，代表一次事件：
1 p x：編號是 $p$ 的飲料賣完了要換成新飲料，新飲料的好喝度是 $x$2 l r：這天早上你要買飲料，你選飲料的範圍是 $[l, r]$ 區間
輸入範圍：
- $1 \le N, Q \le 5 \times 10^ 5$
- $|a_i|, |x| \le 2000$
- $1 \le p \le N$
- $1 \le l \le r \le N$
Output Format
對於每個第二種事件，輸出一個整數代表那次買飲料你獲得了多少滿足度。
Sample Input 1
4 3 1 5 2
5
2 1 5
2 2 4
1 3 7
2 1 5
2 2 4
Sample Output 1
23
169
71
Sample Input 2
-2 -6 1 3 0 -4 -10 -4 9 -9
10
2 3 10
2 1 6
1 7 7
1 10 -10
2 6 7
2 1 9
2 3 7
1 2 -10
2 1 7
2 5 9
Sample Output 2
-1
-28
-98
-13
-77
-49
Hints
這間飲料店到底是哪個 A 子開的呢？
你陷入了沉思。不過，飲料很好喝，希望不要再賣完了。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資。 | 0 |
| 2 | 0~6 | $N, Q \le 500$ | 1 |
| 3 | 0~11 | $N, Q \le 5000$ | 9 |
| 4 | 0~16 | 無特別限制。 | 90 |