**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();↵
}↵
↵
~~~~~↵
↵
↵
↵
↵
↵
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();↵
}↵
↵
~~~~~↵
↵
↵
↵
↵
