競技プログラミング用 知識集積所
ABC423E - Sum of Subarrays
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
まず、式変形が必要。
Σ[l=L->R] Σ[r=l->R] Σ[j=l->r] A[j]
でA[i]が何回足されるかを考える。
まず、l>=Lであるため、i<Lであれば明らかに0回。
同様に、i>Rである場合も0回。
L≦i≦Rである場合は、l≦i≦rであるようなlとrの取り方の個数だけ足すことになる。
つまり、(i-L)*(R-i)回足すことになる。
まず、l>=Lであるため、i<Lであれば明らかに0回。
同様に、i>Rである場合も0回。
L≦i≦Rである場合は、l≦i≦rであるようなlとrの取り方の個数だけ足すことになる。
つまり、(i-L)*(R-i)回足すことになる。
これを、添字を1ずらした上で区間[L,R)で扱えるように考えると、
a[i]*{(-1)*i^2+(L+R-1)*i-R*(L-1)}
の総和を求める問題となる。
これは、
- a[i]*i^2 + (L+R-1)*a[i]*i - R*(L-1)*a[i]
の[L,R)での和と考えると、
- a[i]*i^2の累積和
- a[i]*iの累積和
- a[i]の累積和
を個別に用意しておくことで計算可能。
解答例
解答例
（命名規則の都合で、問題のLとRをlとrにしてある。問題のlとrはコードに登場しない。）
（命名規則の都合で、問題のLとRをlとrにしてある。問題のlとrはコードに登場しない。）
注意点
- long long型を用いる
