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<int> vi;
typedef vector<ll> 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<int> 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;
}

2. Let there be an array of N integers. You need to sum of (AND , OR) of all subarrays. 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<int> vi;
typedef vector<ll> 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<int> 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;

void solve() {
    // Let there be an array of N integers.
    //You need to sum of (AND , OR) of all subarrays.
    // i will use dp for this
    int n;
    cin>>n;
    IN_VEC(a,n);
    vector<vi> t(32,vi(n,0));
    for(int i=0;i<n;++i){
        for(int j=0;j<32;++j){
            if(a[i]&(1ll<<j)) t[j][i]=1;
        }
    }
    int res=0;
    for(int b=0;b<32;++b){
        int ans=0;
        // 1. let cnt1[i] be # j's st j<i & sum[j,i)>0
        vi cnt1(n+1,0ll), cnt2(n+1,0ll);
        for(int i=1;i<=n;++i){
            if(t[b][i-1]) cnt1[i]=i;
            else cnt1[i]=cnt1[i-1];
        }
        // 2. let cnt2[i] be # j's st j<i & sum[j,i)==j-i
        for(int i=1;i<=n;++i){
            if(t[b][i-1]) cnt2[i]=cnt2[i-1]+1ll;
            else cnt2[i]=0ll;
        }
        for(int i=0;i<n;++i){
            if(t[b][i]) ans+= i+2ll+cnt2[i];
            else ans+= cnt1[i];
        }
        res+= ans*(1ll<<b);
    }
    cout<<res<<endl;
}

int32_t main() {
    fastio();
    solve();
}