殊途同歸（二）[BJOI2018] 鏈上二次求和

09-13

4 人贊了文章

題意：給一條鏈，每一個點賦予一個權值，支持操作和查詢。

std：區間修改在答案上的體現是區間上加了一個分段二次函數，然後以此為 lazy 標籤維護線段樹來求和即可。

我承認我在講題的時候划水了……因為當時就覺得 std 的思路不是唯一的，於是就沒有仔細推……

我的做法：

首先我在考省選準備開這題時候已經只剩下 40min 左右了，之前花費了太多時間在高斯消元上（高斯消元還是救了我一命啊），搞出正解非常懸了，所以就推了一個較高分的暴力。

考慮在 $u$ 節點單點修改，對於答案數組 $a_l$ 處的貢獻，即該節點有多少條長度為 $l$ 的路徑穿過它。可以考慮這一條路徑的最左端點位置取值範圍。

最左可以取到 $max(1,u-l+1)$ ，而最右可以取到 $min(u,n-l+1)$ ，故對答案的貢獻是 $min(u, n - l + 1) - max(1, u - l + 1) + 1$ 。

這個東西畫出關於 $l$ 的函數圖像應該是一個三段函數（通常），兩個拐點顯然在 min 中兩項相等或 max 中兩項相等時候取得。

不過直接分析也可以求出來上面這個式子對應的差分，其實是在答案數組上影響了其二階差分，即 $Delta_2 a_1=1$ ， $Delta_2 a_{u+1} = -1$ ， $Delta_2 a_{n-u+2} = -1$ 。

那麼對於一次單點修改，我們可以 $Theta(1)$ 更新差分數組，然後 $Theta(n)$ 重構答案數組順便再掃一遍前綴和。對於區間修改，就先統一更新，再重新重構就可以做到單次修改 $Theta(n)$ 完成而單次查詢 $Theta(1)$ 完成。這個做法按照分點拿到了 50 分。

而為了通過此題，注意到區間修改的本質是增進了一個維度，結合前綴和我們實際需要在一個四階差分上做單點修改。因此引出了本文實際想探討的小問題：用數據結構一般性地維護高階前綴和。

其實曾經研究的樹狀數組進行區間修改區間查詢，就是在二階前綴和上的探索。注意到前綴和或差分具有可累加性，不妨直接討論對於一個數列 $a_1=1$ ， $i>2,a_i=0$ 的數列的 $k$ 階前綴和 $sigma_{k,n}=sum_{i=1}^nsigma_{k-1,i}$ 的表示。

容易注意到 $sigma_{1,n}=1,sigma_{2,n}=n$ ，而結合小學知識我們進一步知道 $sigma_{3,n}=frac{n(n+1)}2$ 以及 $sigma_{4,n}=frac{n(n+1)(n+2)}6$ 。

其實研究到這裡已經夠用了，我們只需要用樹狀數組累加地維護一個 $k-1$ 階多項式，那麼多項式平移時預處理需要 $Theta(nk^2)$ ，而單次修改和查詢都是 $Theta(klog n)$ 的。

其實更高階的式子也能猜到，根據前綴和的形式 $sigma_{k,n}= sigma_{k,n-1} + sigma_{k-1,n}$ 可以歸納證明 $sigma_{k,n} = inom{n+k-2}{k-1} =frac 1{(k-1)!}n(n+1) cdots (n+k-2)$ 。

實測跑得還是比較快的：https://loj.ac/submission/95463