今年BJ省選某題的弱化版……

這看起來就沒那么難了，有幾種方法維護，這里提兩種。

?

第一種（傻逼的我寫的）

維護 一維&二維前綴和。

對于一個長度為$m$的序列$b_1,b_2,...,b_m$，

由于 二維前綴和$=b_1*m+b_2*(m-1)+...+b_m*1$，

每一項都和$m$有關系，而$m$可以是任意子區間的長度，于是很不好維護。

我們可以解除這些數與$m$的關系，最簡單的方法就是把它們反過來維護。

我們已經維護了一維前綴和（即$b_1 to b_m$的和），

所以我們可以反過來維護 $b_1*0+b_2*1+...+b_m*(m-1)$ 的和，二維前綴和就是$(b_1+b_2+...+b_m)*m-[b_1*0+b_2*1+...+b_m*(m-1)]$。

這樣就有一個全局維護的方法能夠解除每個數與$m$的直接關系，而只跟每個數本身的位置$-1$有關系，即線段樹維護每個區間$[l,r]$的一維前綴和 $b_l+b_{l+1}+...+b_r$ 與二維前綴和 $b_l*(l-1)+b_2*l+...+b_m*(r-1)$。

然后我還寫了對拍，包括最終測評數據在內，所有$n,m\le 5000$的數據都過了……我沒理解啊……

因為測了大數據$n,m=100000$后我就WA上天了（基本上沒有跟標答一致的輸出）。

后來浪費時間查了好久，發現增加線段樹上的二維前綴和時，求等差數列?$(l-1)+l+...+(r-1)$?的和的通項公式中有個$÷2$，而除法不能隨便取模（被除數和除數中任意組成部分都不能取模）……

應該是這么寫 $((((ll)(l-1+r-1)*(r-l+1))>>1)\%mod)$

我是這么寫的?$((((ll)(l-1+r-1)*(r-l+1)\%mod)>>1)$

數學沒學好$=GG$

改完就差不多了吧。

也可以把除以$2$改成乘$2$的逆元，這樣兩邊就可以隨便取模了。$2$的逆元也比較簡單，就是$\frac{mod+1}{2}$。

?

第二種（機房dalao們寫的）

換一種反過來維護的方式。

我們考慮當一個數

轉載于:https://www.cnblogs.com/scx2015noip-as-php/p/9822215.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的【2018.10.20】noip模拟赛Day3 二阶和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。