某島

… : "…アッカリ~ン . .. . " .. .
September 3, 2013

SPOJ 9138. Pyramid Sums 2

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