1. Count no. of hills in an array a, i.e. # no. of triplets (i,j,k) s.t. i<j<k & a[i]<=a[j]>=a[k]

Solution: ~~~~~

include <bits/stdc++.h>

using namespace std;

define fastio() ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

define int long long

define double long double

typedef long long ll; typedef unsigned long long ull;

typedef vector vi; typedef vector vll; typedef pair<int,int> pii; typedef pair<ll,ll> pll;

define pb push_back

define ff first

define ss second

define all(x) (x).begin(), (x).end()

define rall(x) (x).rbegin(), (x).rend()

define YES cout << "YES\n"

define NO cout << "NO\n"

define endl '\n'

define IN_VEC(v,n) vector v(n); for(auto &i : v) cin >> i;

define IN_ARR(arr,n) for(int i=0;i<n;i++) cin >> arr[i];

const ll INF = 1e18; const int MOD = 1e9 + 7; vi t1; void update(int pos,int x,int lx,int rx){ if(lx==rx-1){ t1[x]+=1ll; return; } int mid=(lx+rx)/2; if(pos<mid) update(pos,2*x+1,lx,mid); else update(pos,2*x+2,mid,rx); t1[x]=t1[2*x+1]+t1[2*x+2]; } int sum(int x,int lx,int rx,int l,int r){ if(r<=lx || l>=rx) return 0; if(l<=lx && rx<=r) return t1[x]; int mid=(lx+rx)/2; return sum(2*x+1,lx,mid,l,r)+sum(2*x+2,mid,rx,l,r); } void solve() { // 1. Hills — # (i,j,k) st i<j<k & a[i]<a[j]>a[k] int n; cin>>n; IN_VEC(a,n); // compress a st 0<=a[i]<=n-1 vi rank=a; sort(all(rank)); rank.erase(unique(all(rank)),rank.end()); for(int i=0;i<n;++i){ a[i]=lower_bound(all(rank),a[i])-rank.begin(); } // we build two segment trees l,r intialised as 0 t1.assign(n,0ll); vi l(n),r(n); for(int i=0;i<n;++i){ l[i]=sum(0,0,n,0,a[i]); update(a[i],0,0,n); } t1.clear(); t1.assign(n,0ll); for(int i=n-1;i>=0;--i){ r[i]=sum(0,0,n,a[i]+1,n); update(a[i],0,0,n); } int ans=0; for(int i=0;i<n;++i){ ans += l[i]*r[i]; } cout<<ans<<endl; }

int32_t main() { fastio(); solve(); return 0; } ~~~~~