AtCoder Grand Contest 005: B - Minimum Sum

,

https://beta.atcoder.jp/contests/agc005/tasks/agc005_b

std::mapに持ちながら端から舐めていってもいける気がする。

solution

分割統治。数列の区間中で一番小さい数を含むか含まないかで分け、含まないなら小さくなった区間について再帰。区間への分割点の集合を持つようにすれば非再帰になり実装も楽。$O(N \log N)$。

implementation

#include <cstdio>
#include <queue>
#include <set>
#include <tuple>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using ll = long long;
using namespace std;
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;

int main() {
    // input
    int n; scanf("%d", &n);
    vector<int> a(n); repeat (i, n) scanf("%d", &a[i]);
    // solve
    reversed_priority_queue<pair<int, int> > que;
    repeat (i, n) {
        que.emplace(a[i], i);
    }
    set<int> sep;
    sep.insert(-1);
    sep.insert(n);
    ll result = 0;
    while (not que.empty()) {
        int a_i, i; tie(a_i, i) = que.top(); que.pop();
        auto it = sep.upper_bound(i);
        int r = *it;
        int l = *(-- it) + 1;
        result += (i - l + 1) * (ll) (r - i) * a_i;
        sep.insert(i);
    }
    // output
    printf("%lld\n", result);
    return 0;
}