Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

AGC005-B 「Minimum Sum」 (400)

600点はあると思う。

問題リンク

概要

数列 (1, 2, \dots, N)の順列 aが与えられる。

 \displaystyle \sum_{l = 1}^{N} \sum_{r = l}^{N} min(a_l, \dots, a_r)

を求めよ。

制約

  •  1 \leq N \leq 2 \times 10^5

解説

数式が表しているのは、「 aについて考えうる全ての区間に対して、その最小値を足し合わせたもの」という意味。区間は全部で N (N + 1) / 2個あるので、毎回愚直に全要素を見ていると計算量 O(N^3)で全然間に合わない。

そこでまず考えられるのが、セグ木による高速化である。セグ木は区間最小値を O(\log N)で求められるので、計算量は O(N^2 \log N)まで落ちる。しかしこれでも間に合わない。

ここで根本的な発想の転換が必要となる。「各区間の最小値はいくつか?」ではなく代わりに「値 iはいくつの区間の最小値になるか?」が求まれば、 i \times (最小値になる区間の数)を足し合わせることで答えが求まる。

さらにこの区間数は、左右両方について「一番近くにある自分より小さい要素」の位置が分かれば以下のように求められる。

f:id:misteer:20180928082257p:plain

ただこれを求める方法が結構閃きというか知識が必要で、小さい方から値を数列に加えていく必要がある。小さい方から値を加えていくと、「既に数列に存在している値は全て今見ている値より小さい」という性質が成り立つ。よって「既に加えられたもので一番近くにある要素の位置」を求めるだけで十分になる。

これはsetにindexを突っ込んでいけば、lower_boundを使うことで O(\log N)で検索できるため全体の計算量は O(N \log N)まで落ちて十分間に合う。

f:id:misteer:20180928082318p:plain

上の図がそれを実践した例で、上段が数列、下段がindexとなっている。また、上のように両端に0があると仮定すると実装しやすい。

実装例

#include <iostream>
#include <set>
using namespace std;
using ll = long long;

int main() {
    int N;
    cin >> N;
    
    ll place[N + 1];
    // place[i]...値iのaにおけるindex
    
    for (int i = 1; i <= N; ++i) {
        ll a;
        cin >> a;
        place[a] = i;
        // 保持するのはindexなので、ここが普通と逆なことに注意
    }

    ll ans = 0;
    set<ll> used = {0, N + 1};
    // すでに見た要素のindexを保持する
    
    for (int i = 1; i <= N; ++i) {
        ll r, l;
        
        auto itr = used.lower_bound(place[i]);
        r = *itr;
        // lower_boundで右端を調べる(upper_boundでもいい)
        l = *(--itr);
        // その1個手前が左端
        
        ans += i * (place[i] - l) * (r - place[i]);
        used.insert(place[i]);
    }

    cout << ans << endl;
    return 0;
}

lower_boundは調べたい値「以上」の要素、upper_boundは調べたい値「より大きい」要素を検索する。今回の場合は同値なものが存在しないのでどちらでもいいが、この辺は常に意識したい。

あとlower_bound(set.begin(), set.end())をやらないように注意。これの計算量は O(\log N)ではなく O(N)である。

感想

  • 「値を小さい方から入れていく」というのは一種の典型なのだろう
  • それでも知らなきゃ思いつくのは困難だし、400点にしては難しすぎる。