yukicoder：No.1096 Range Sums - kacho65535の競プロメモ

一部空のコードブロックがありますが、texの数式を正しく表示させるための応急処置なので許してください...

問題概要

yukicoder.me

$N$ 個の要素 $A_{i}$ からなる数列がある。

$\displaystyle \sum_{L=1}^{N} \sum_{R=L}^{N} \sum_{i=L}^{R} {A_{i}}$ を求めよ。

制約

$1 \leq N \leq 2×10^{5}$
$0 \leq A_{i} \leq 10^{6}$
答えは $10^{18}$ 以下に収まる

解法

まず、初期状態では範囲が広い $Σ$ が $3$ つ付いていて、愚直にやると計算に $O(N^{3})$ かかる。

累積和を用いれば各 $\displaystyle \sum_{i=L}^{R} {A_{i}}$ が $O(1)$ で計算できるようになるが、左側に $Σ$ が $2$ つ残っているので普通にやると間に合わない。

こういった問題でよく用いられる典型考察として、各要素が何回足されるかを考えるというものがある。

この考察が役立つAtcoder上の問題(ネタバレ防止のため隠してあります)

AGC005 B - Minimum Sum
Aiが答えに加算される回数を考えるところが本質です。
[https://atcoder.jp/contests/agc005/tasks/agc005_b]
ABC140 E - Second Sum
Minimum Sumの完全上位互換です。まだ解けてません(←?)
[https://atcoder.jp/contests/abc140/tasks/abc140_e]
第6回 ドワンゴからの挑戦状 予選 B - Fusing Slimes
スライムがxi,x(i+1)間を移動する確率をそれぞれ求めるのが本質という点で類似しています。
[https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_b]

$A_{i} (1 \leq i \leq N)$ は、 $L$ が $1$ 以上 $i$ 以下かつ $R$ が $i$ 以上 $N$ 以下のときにのみ足されるので、合計で $i(N-i+1)$ 回足されることになる。

実装上では $0$ -indexedで計算する必要があることに注意しながら足し合わせていけばよい。

計算量は $O(N)$ 。

コード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define mod 1000000007ll
#define loop(i, n) for (int i = 0; i < n; i++)
#define all(v) v.begin(), v.end()
#define putout(a) cout << a << '\n'
#define Sum(v) accumulate(all(v), 0ll)

int main()
{
    ll N, a, ans = 0;
    cin >> N;
    loop(i, N)
    {
        cin >> a;
        ans += a * (1 + i) * (N - i);
    }
    putout(ans);
    return 0;
}

課題残ってるけど毎日 $1$ 問位なんか解説書いたほうがいいかなと思って、投稿...

い、息抜き代わりということで...