Submission #2242729

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=(0);(i)<(int)(n);++(i))
using ll = long long;
using P = pair<int, int>;
using namespace std;

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

struct SegmentTree {
    int n;
    vector<int> node;
    SegmentTree(vector<int> v) {
        n = 1;
        while (n < v.size()) n *= 2;
        node.resize(2*n-1, INT_MAX);
        for (int i=0; i<v.size(); ++i) node[i+n-1] = v[i];
        for (int i=n-2; i>=0; --i) node[i] = min(node[i * 2 + 1], node[i * 2 + 2]);
    }
    SegmentTree(int N) {
        n = 1;
        while (n < N) n *= 2;
        node.resize(2*n-1, INT_MAX);
    }
    // x番目の要素をvalに更新
    void update(int x, int val) {
        x += (n - 1);
        node[x] = val;
        while (x > 0) {
            x = (x - 1) / 2;
            node[x] = min(node[2 * x + 1], node[2 * x + 2]);
        }
    }
    // [a, b)の中の要素の最小値を答える
    // k := 自分がいるノードのインデックス
    int query(int a, int b, int k=0, int l=0, int r=-1) {
        if (r < 0) r = n;
        if (r <= a || b <= l) return INT_MAX;
        if (a <= l and r <= b) return node[k];
        int vl = query(a, b, 2*k+1, l, (l+r)/2);
        int vr = query(a, b, 2*k+2, (l+r)/2, r);
        return min(vl, vr);
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    rep(i, n) cin >> v[i];
    SegmentTree st(v);
    ll ans = 0;
    for (int l=0; l<n; ++l) {
        for (int r=l; r<n; ++r) {
            ans += st.query(l, r+1);
        }
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result