Untitled
unknown
c_cpp
2 years ago
1.8 kB
6
Indexable
#include "bits/stdc++.h" using namespace std; using ll = long long; using ull = unsigned long long; using db = long double; using pii = pair<int, int>; using pll = pair<ll, ll>; using pdd = pair<db, db>; using tiii = tuple<int, int, int>; using str = string; #define vt vector #define pb push_back #define eb emplace_back #define ins insert #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define sz(x) (int)x.size() #define mp make_pair #define mt make_tuple #define fi first #define se second constexpr int maxN = 1e5; vt<int> parent(maxN), s(maxN, 1); int leader(int v) { return (parent[v] == v ? v : parent[v] = leader(parent[v])); } void merge(int a, int b) { a = leader(a); b = leader(b); if (s[a] < s[b]) swap(a, b); s[a] += s[b]; parent[b] = a; } void solve() { iota(all(parent), 0); int n; cin >> n; vt<int> p(n); vt<int> inds(n); for (int i = 0; i < n; i++) { cin >> p[i]; p[i]--; inds[p[i]] = i; } ll ans = 0; for (int i = 0; i < n; i++) { ll cntL = 1, cntR = 1; int id = inds[i]; if (id > 0 && i > p[id - 1]) { cntL += s[leader(p[id - 1])]; merge(i, p[id - 1]); } if (id < n - 1 && i > p[id + 1]) { cntR += s[leader(p[id + 1])]; merge(i, p[id + 1]); } ans += cntL * cntR * (i + 1); } cout << ans; } signed main() { ios::sync_with_stdio(false); cin.tie(NULL); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int tests = 1; // cin >> tests; while (tests--) { solve(); } return 0; }
Editor is loading...