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

Posted by xiaodao
Category: SPOJ