Submission #1439441

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
using namespace std;

typedef long long int ll;
#define rep(i,a,n) for(int i=a; i<n; i++)
#define repq(i,a,n) for(int i=a; i<=n; i++)
#define repr(i,a,n) for(int i=a; i>=n; i--)
#define int long long int
constexpr ll INF = 1001001001001001LL;

// Sparse Table 構築 O(N log N), クエリ O(1)
// 配列で init することでテーブルを構築し、
// [l, r) のクエリに O(1) でこたえられる
// Verified: Codeforces #361 Div.2 D: Friends and Subsequences

constexpr int SIZE = 200010;
constexpr int LOGS = 20;

template <typename T>
struct SparseTable_min {
    T a[SIZE];
    int table[SIZE][LOGS], log_table[SIZE];
    int n;
    void init(vector<T> p) {
        n = (int)p.size();
        for(int i=0; i<n; i++) {
            a[i] = p[i];
            table[i][0] = i;
        }
        for(int i=2; i<=n; i++) {
            log_table[i] = log_table[i>>1] + 1;
        }

        for(int k=1; (1<<k)<=n; k++) {
            for(int i=0; i+(1<<(k-1))<=n; i++) {
                int x = table[i           ][k-1];
                int y = table[i+(1<<(k-1))][k-1];
                if(a[x] <= a[y]) table[i][k] = x;
                else table[i][k] = y;
            }
        }
    }

    // 半開区間 [l, r) における最大値のインデックスを返す
    int query(int l, int r) {
        int d = log_table[r - l];
        int x = table[l       ][d];
        int y = table[r-(1<<d)][d];
        if(a[x] <= a[y]) return x;
        else return y;
    }
};

SparseTable_min<int> sp;

signed main() {
    int N; cin >> N;
    vector<int> v(N);
    rep(i,0,N) cin >> v[i];
    sp.init(v);

    int ans = 0;
    rep(i,0,N) {
        int vl, vr;
        int lb = -1, ub = i;
        while(ub - lb > 1) {
            int mid = (ub + lb) / 2;
            if(v[sp.query(mid, i)] < v[i]) lb = mid;
            else ub = mid;
        }

        vl = i - lb;

        lb = i, ub = N;
        while(ub - lb > 1) {
            int mid = (ub + lb) / 2;
            if(v[sp.query(i, mid+1)] < v[i]) ub = mid;
            else lb = mid;
        }

        vr = ub - i;
        // printf("vl = %lld, vr = %lld\n", vl, vr);

        ans += (vl * vr * v[i]);
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result