Brief description:
…. 維護一個數列。。支持以下兩個操作。。。
。。。詢問區間和。
。。。以 c 為中心建一個寬度為 w 。高為 (w+1)/2 的等邊三角形(w 為奇數)。。。
Analysis:
做法 1:線段樹
做法 2:一階差分後線段樹(。。。標記更直接些。。。)
做法 3:二階差分後直接樹狀數組。。。
$$!\begin{align*}\begin{split}\sum_{1\leq i\leq n}A_i &= \sum_{1\leq i\leq n}\sum_{1\leq j\leq i}\sum_{1\leq k\leq j} \nabla^{2} A_k \\ &= \sum_{1\leq k\leq n}\sum_{k\leq j\leq n}\sum_{j\leq i\leq n} \nabla^{2} A_k \\ &= \sum_{1\leq k\leq n} \binom{n-k+2}{2} \nabla^{2} A_k \\ &= \sum_{1\leq k\leq n} \frac{k^2 – (2n+3)k +(n+1)(n+2)}{2} \nabla^{2}A_k\end{split}\end{align*}$$
。。這裡。。我們需要看的是 k 的次冪前面的係數。。用三個樹狀數組分別維護這三項。。。
const int N = 1000009; const int n = 1000000; LL S0[N], S1[N], S2[N]; int a, b, c, w; void Add(LL S[], int x, LL d){ for (;x<=n;x+=low_bit(x)) S[x] += d; } LL Sum(LL S[], int x){ LL z=0; for (;x;x^=low_bit(x)) z += S[x]; return z; } void Add(int x, LL d){ Add(S0, x, d), Add(S1, x, d*x), Add(S2, x, d*x*x); } LL Sum(int x){ return Sum(S0, x)*(x+1)*(x+2) - Sum(S1, x)*(x*2+3) + Sum(S2, x); } void Add(int l, int r, LL d){ Add(l, d), Add(r+1, -d); } LL Sum(int l, int r){ return Sum(r) - Sum(l-1); } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif char cmd[9]; Rush{ RS(cmd); if (cmd[0] == 'b'){ RD(c, w), w = (w-1)/2; Add(c-w, c, 1), ++c, Add(c, c+w, -1); //# } else { RD(a, b); OT(Sum(a, b)/2); } } }
思考。。。考慮如果維護的是高階等差如何還原到原數列。。。有。。
$$!\begin{align*}\begin{split}\sum_{1\leq i\leq n} A_i &= \sum_{1\leq i\leq n} \binom{n-i+k}{k} \nabla^{k} A_i \\&= \sum_{1\leq i\leq n} \frac{\prod_{n+1\leq j \leq n+k}(j-i)}{k!} \nabla^{k}A_i\end{split}\end{align*}$$
。。。最後上面的那個部分似乎很不好展開。。。只能一層一層枚舉?、、。。、、
…
http://www.spoj.com/problems/PYRSUM/
。。這個版本總數據量增大。。。但是每輪的操作和詢問變少。。。上面只有最後純樹狀數組的方法可以過。。。
。。。更好的方法是遇到詢問的時候。。直接枚舉之前出現的每個操作累計貢獻。。
https://gist.github.com/lychees/6420822