ABC140 E - Second Sum

問題

atcoder.jp

解法

• 範囲を列挙してそこに含まれる2番目に大きい数を探すのではなく、順列の値X[i]それぞれに対してX[i]が2番目に大きくなるような範囲を数え上げる
• X[i]より大きい値を一つだけ含み、j<=iとなる最小値jを求める。また、X[i]より大きい値を一つも含まず、i<=kとなる最大値kを求める。
• また、X[i]より大きい値を一つだけ含み、i<k'となる最大値k'を求める。また、X[i]より大きい値を一つも含まず、j'<=iとなる最小値j'を求める。
• jk+j'k'がX[i]が2番目に大きくなるような範囲の数になる。

コード

#include <bits/stdc++.h>
#include <atcoder/all>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())

using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

void print() {
  cout << endl;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
  cout << head;
  if (sizeof...(tail) != 0) cout << " ";
  print(forward<Tail>(tail)...);
}

template <class T>
void print(vector<T> &vec) {
  for (auto& a : vec) {
    cout << a;
    if (&a != &vec.back()) cout << " ";
  }
  cout << endl;
}

template <class T>
void print(vector<vector<T>> &df) {
  for (auto& vec : df) {
    print(vec);
  }
}

int main() {
  int n;
  cin >> n;
  vi a(n), idx(n);
  rep(i,n){
    cin >> a[i];
    a[i]--;
    idx[a[i]]=i;
  }
  set<int> s;
  ll ans = 0;
  for(ll x = n-1;x>=0;x--){
    int i = idx[x];
    s.insert(i);
    vi l(2,-1);
    vi r(2,n); 

    auto it_l = s.find(i);
    rep(j,2){
      if(it_l == s.begin())break;
      it_l--;
      l[j] = *it_l;
    }
    
    auto it_r = s.find(i);
    rep(j,2){
      it_r++;
      if(it_r == s.end())break;
      r[j] = *it_r;
    }

    vl cntL(2), cntR(2);
    cntL[0] = i-l[0];
    cntL[1] = l[0]-l[1];
    cntR[0] = r[0]-i;
    cntR[1] = r[1]-r[0];
    ans+= (x+1)*(cntL[0]*cntR[1] + cntL[1]*cntR[0]); 
  }
  cout<<ans<<endl;
  return 0;
}