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
