$\displaystyle \sum_{i=0}^{n-1}\sum_{j=i}^{n-1} f(A_i,\ldots, A_j)$ という形の二重和について
共通的な話
-
二重和を表にしたもの
| i ＼ j |
0 |
1 |
2 |
| 0 |
A[0] |
A[0]A[1] |
A[0]A[1]A[2] |
| 1 |
|
A[1] |
A[1]A[2] |
| 2 |
|
|
A[2] |
-
総和の入れ替え
-
全体的な方針
- 数列の各項の寄与を考える
- double counting をする
- 累積xxを使う
- 漸化式を作る
- 遅延セグ木を使う
問題例
- $\displaystyle \sum_{i=0}^{n-1}\sum_{j=i}^{n-1} (A_i+\cdots +A_j)$
- $\displaystyle \sum_{i=0}^{n-1}\sum_{j=i}^{n-1} (A_i\times \cdots \times A_j)$
- $\displaystyle \sum_{i=0}^{n-1}\sum_{j=i}^{n-1} \max\{A_i,\ldots, A_j\}$
- $\displaystyle \sum_{i=0}^{n-1}\sum_{j=i}^{n-1} (A_i\oplus \cdots \oplus A_j)$
- $\displaystyle \sum_{i=0}^{n-1}\sum_{j=i}^{n-1} (A_i,\ldots, A_j) \text{ を文字列結合して10進整数と解釈したもの}$
todo: 種類数も書く。
解けてない問題
- $\displaystyle \sum_{i=0}^{n-1}\sum_{j=i}^{n-1} (A_i,\ldots, A_j) \text{の転倒数}$ (数列 $A$ の成分はすべて相異なる)
類題