Sum of Subarrays の解説

(a_i, a_i+1, a_i+2..a_i+d-1) のd個の和を求めるクエリが与えられた時のことを考える。

その中の、a_kについて、クエリの中で何回足されるかを考えると、 (a_kより左にある数 + 1) * (a_kより右にある数 + 1)になる。

これを式に落とし込むと、

$\sum_i (i + 1 - l) * (d - i + l) * Ai$

で、$a = 1 - l$, $b = d + l$としてあげれば

$ab\sum_i Ai + (b - a)\sum iAi - \sum_i i^2Ai$

とできるので、これらを前もって計算しておくことで高速にそれぞれのクエリに回答できる。

fn main() {
    input! {
        n: usize,
        q: usize,
        a: [isize; n],
        lr: [(Usize1, Usize1); q]
    }
    let (one, two, three) = {
        let mut one = vec![];
        let mut two = vec![];
        let mut three = vec![];
        for i in 0..n {
            one.push(a[i]);
            two.push(i as isize * a[i]);
            three.push(i as isize * i as isize * a[i]);
        }
        let one = Segtree::<M>::from(one);
        let two = Segtree::<M>::from(two);
        let three = Segtree::<M>::from(three);
        (one, two, three)
    };
    for &(l, r) in lr.iter() {
        let diff = (r - l + 1) as isize;
        let a = 1 - l as isize;
        let b = diff + l as isize;
        let sum1 = one.prod(l..=r);
        let sum2 = two.prod(l..=r);
        let sum3 = three.prod(l..=r);

        let p1 = a * b * sum1;
        let p2 = (b - a) * sum2;
        let p3 = sum3;

        let ans = p1 + p2 - p3;
        println!("{}", ans);
    }
}