AC代碼：

https://codeforces.com/contest/1814/submission/203771436

題意：

給出了一個由n個頂點和n?1條邊組成的無向圖。第i條邊的權重為ai；它連接頂點i和i+1。

最初，每個頂點都包含一個芯片。每個芯片上都寫有一個整數(shù)；寫在第i個頂點的芯片上的整數(shù)是i。

在一個操作中，您可以選擇一個芯片（如果單個頂點中有多個芯片，則可以選擇其中的任何一個），

并將其沿圖形的一條邊移動。此操作的成本等于邊的權重。

圖形的成本是滿足以下條件的一系列此類操作的最小成本：

在執(zhí)行所有操作之后，每個頂點恰好包含一個芯片，并且每個芯片上的整數(shù)不等于該芯片所在頂點的標號。

您將得到以下形式的q個查詢：

k x-將第k條邊（連接頂點k和k+1的邊）的權重更改為x。

每次查詢后，求該圖形的成本。

題解：

矩形乘法 + 線段樹

矩陣乘法順序

?base[1]* base[2]*... *? base[n]

?所以 val[1].a[0][1]*2 為 fn,?

?val[1].a[1][1]*2 為 f[n-1], 即頂點(a2,a3,...,an)的最小權重。