PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Soumyadeep Pal
Tester: Manan Grover, Lavish Gupta
Editorialist: Devendra Singh
DIFFICULTY:
2645
PREREQUISITES:
Segment trees, stack data structure, Divide and Conquer algorithm paradigm
PROBLEM:
You are given a permutation P of N integers from 1 to N.
The weight of a subarray [L, R] (1\le L \le R \le N) is defined as |i - j| where i denotes the index of the maximum element and j denotes the index of the minimum element in the subarray [L,R].
Find the sum of the weights of all subarrays of the given permutation.
Note that, |X| denotes the absolute value of a number X. For example, |-4| = 4 and |7| = 7.
EXPLANATION:
Let us solve the problem by calculating the contribution of each index i of the array to the answer. An index i affects the answer only if A_i is either the maximum element or minimum element of some subarray.
Let i_{max} be the index of maximum element of the array A. Then i_{max} is the index of maximum element for every subarray which begins to the left of i_{max} (including i_{max}) and ends on the right of i_{max} (including i_{max}). i_{max} divides the array into two components: the right component and the left component. We will always iterate on the component which contains less number of elements.
Let the left component contain less number of elements.
Let us calculate the contribution of i_{max} to the answer .
All the subarrays with starting index = i_{max} and ending index at i_{max}+1,… N contribute -i_{max} each as all of these subarrays will have maximum element index < minimum element index.
answer -= i_{max} * (N - i_{max})
Iterate over the left component from i = i_{max}-1 to 1 considering index i as the starting index of the subarrays and ending indices at i_{max} to N. Let i_{min} be the index of the minimum element in the subarray A[i,..i_{max}-1] and nxt be the index of an element smaller than A[i_{min}] in the subarray A[i_{max}+1,..., N].Now all subarrays with starting index at i and ending indices at i_{max}, ... nxt-1 will have maximum element at index = i_{max} and minimum element at index = i_{min}. All of these subarrays will have maximum element index > minimum element index and hence each subarray contributes i_{max} to the final answer.
All subarray with starting index at i and ending indices at nxt,..., N will have maximum element at index = i_{max} and minimum element at some index in the subarray [nxt, N]. All of these subarrays have minimum element index > maximum element index and hence each subarray contributes -i_{max} to the final answer
\therefore answer += (nxt - i_{max}) * i_{max} - (N + 1 - nxt) * i_{max}
Similarly, if the right component is smaller
answer += (i_{max}- 1) * i_{max};
Iterate over the right component from i = i_{max}+1 to N . Let i_{min} be the index of the minimum element in the subarray A[i_{max}+1,...,i] and back is the largest index of an element smaller than A_{i_{min}} in the subarray A[1,..., i_{max}-1]
\therefore answer += (back) * i_{max} - (i_{max} - back) * i_{max}
Now, the contribution of each index to the answer from the left component and right component can be calculated by treating them as individual arrays. Recur over the left component and the right component to find the contribution of the indices in them. The contribution for the every index when it is index of the minimum element of some subarray can be done simply by multiplying each of the element by -1 and applying the same algorithm as above.
The next smaller element and last smaller element for each element can be calculated efficiently using stack.
The index of maximum element for any range can be calculated efficiently using a segment tree where each node stores the index of the maximum element its subtree.
For details of implementation, please refer to the solutions attached.
Time complexity proof
Consider two components A and B, with sizes |A| and |B|. WLOG, assume |A|≤|B|. We will iterate over each index in A, doing so is O(|A|) work. Let’s track how many times we iterate over an index. If an index gets iterated over, it means it was in the smaller of two components being considered. So after the iterations, the answer will be calculated for component that is at least twice the size of its original component. The size of a component can only be doubled O(logN) times before it reaches size N. So an index can only be iterated over at most O(logN) times. Thus, when we sum up the work done on each of N indices, we get O(NlogN) complexity.
TIME COMPLEXITY:
O(Nlog(N)) for each test case.
SOLUTION:
Setter's solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 3; // check the limits
long long readInt(long long l, long long r, char endd) {
long long x = 0;
int cnt = 0;
int fi = -1;
bool is_neg = false;
while (true) {
char g = getchar();
if (g == '-') {
assert(fi == -1);
is_neg = true;
continue;
}
if ('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if (cnt == 0) {
fi = g - '0';
}
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || ( cnt == 19 && fi > 1) ));
} else if (g == endd) {
if (is_neg) {
x = -x;
}
// deb(l, r, x);
assert(l <= x && x <= r);
return x;
} else {
assert(false);
}
}
}
long long readIntSp(long long l, long long r) {
return readInt(l, r, ' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l, r, '\n');
}
int n, ans, a[N];
int t[4 * N], nxt[N], back[N];
void build(int n, int b, int e) {
if (b == e) {
t[n] = b;
return;
}
int mid = (b + e) >> 1, l = n << 1, r = l | 1;
build(l, b, mid);
build(r, mid + 1, e);
if (a[t[2 * n]] > a[t[2 * n + 1]])
t[n] = t[2 * n];
else t[n] = t[2 * n + 1];
}
int get(int v, int tl, int tr, int l, int r) {
if (tr < l || tl > r) return -1;
if (l <= tl && tr <= r) {
return t[v];
}
int tm = (tl + tr) / 2;
int L = get(2 * v, tl, tm, l, r), R = get(2 * v + 1, tm + 1, tr, l, r);
if (L == -1) return R;
if (R == -1) return L;
if (a[L] > a[R]) return L;
return R;
}
void fun(int L, int R) {
if (L >= R) return;
int mid = get(1, 1, n, L, R);
if (mid - L < R - mid) {
ans -= mid * (R - mid);
int mn = mid;
for (int i = mid - 1; i >= L; i--) {
if (a[mn] > a[i]) mn = i;
int Nxt = min(R + 1, nxt[mn]);
ans += (Nxt - mid) * mid - (R + 1 - Nxt) * mid;
}
} else {
ans += (mid - L) * mid;
int mn = mid;
for (int i = mid + 1; i <= R; i++) {
if (a[mn] > a[i]) mn = i;
int Back = max(L - 1, back[mn]);
ans += (Back - L + 1) * mid - (mid - Back) * mid;
}
}
fun(L, mid - 1);
fun(mid + 1, R);
}
signed main() {
ios_base :: sync_with_stdio(0);
cin.tie(0);
// #ifndef ONLINE_JUDGE
// freopen("ip7.in", "r", stdin);
// freopen("out7.out", "w", stdout);
// #endif
int t = readIntLn(1, 1e5);
int sum = 0;
while (t--) {
n = readIntLn(1, 5e5);
sum += n;
for (int i = 1; i <= n; i++) {
if (i < n) a[i] = readIntSp(1, n);
else a[i] = readIntLn(1, n);
}
ans = 0;
for (int k = 0; k < 2; k++) {
build(1, 1, n);
vector<int> v;
for (int i = n; i; i--) {
while (v.size() && a[i] < a[v.back()]) v.pop_back();
nxt[i] = v.empty() ? n + 1 : v.back();
v.push_back(i);
}
v.clear();
for (int i = 1; i <= n; i++) {
while (v.size() && a[i] < a[v.back()]) v.pop_back();
back[i] = v.empty() ? 0 : v.back();
v.push_back(i);
}
fun(1, n);
for (int i = 1; i <= n; i++) a[i] *= -1;
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) assert(a[i] == i);
cout << ans << ' ' << '\n';
}
assert(getchar() == -1);
assert(sum <= 5e5);
return 0;
}
Tester-1's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define asc(i,a,n) for(I i=a;i<n;i++)
#define dsc(i,a,n) for(I i=n-1;i>=a;i--)
#define forw(it,x) for(A it=(x).begin();it!=(x).end();it++)
#define bacw(it,x) for(A it=(x).rbegin();it!=(x).rend();it++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lb(x) lower_bound(x)
#define ub(x) upper_bound(x)
#define fbo(x) find_by_order(x)
#define ook(x) order_of_key(x)
#define all(x) (x).begin(),(x).end()
#define sz(x) (I)((x).size())
#define clr(x) (x).clear()
#define U unsigned
#define I long long int
#define S string
#define C char
#define D long double
#define A auto
#define B bool
#define CM(x) complex<x>
#define V(x) vector<x>
#define P(x,y) pair<x,y>
#define OS(x) set<x>
#define US(x) unordered_set<x>
#define OMS(x) multiset<x>
#define UMS(x) unordered_multiset<x>
#define OM(x,y) map<x,y>
#define UM(x,y) unordered_map<x,y>
#define OMM(x,y) multimap<x,y>
#define UMM(x,y) unordered_multimap<x,y>
#define BS(x) bitset<x>
#define L(x) list<x>
#define Q(x) queue<x>
#define PBS(x) tree<x,null_type,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define PBM(x,y) tree<x,y,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define pi (D)acos(-1)
#define md 1000000007
#define rnd randGen(rng)
long long readInt(long long l, long long r, char endd) {
long long x = 0;
int cnt = 0;
int fi = -1;
bool is_neg = false;
while (true) {
char g = getchar();
if (g == '-') {
assert(fi == -1);
is_neg = true;
continue;
}
if ('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if (cnt == 0) {
fi = g - '0';
}
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if (g == endd) {
assert(cnt > 0);
if (is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret = "";
int cnt = 0;
while (true) {
char g = getchar();
assert(g != -1);
if (g == endd) {
break;
}
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
I cal(I l,I r,OM(P(I,I),I) &mpp,I nx[],I pr[]){
if(r<l){
return 0;
}
I m=mpp[{l-1,r+1}];
I ans=cal(l,m-1,mpp,nx,pr)+cal(m+1,r,mpp,nx,pr);
if(l+r<2*m){
ans+=m+1;
I x=m;
while(x<=r){
I y=min(nx[x],r+1);
I z=max(pr[x],l-1);
ans+=(2*z-l-m+1)*(m+1)*(y-x);
x=y;
}
}else{
ans-=m+1;
I x=m;
while(x>=l){
I y=max(pr[x],l-1);
I z=min(nx[x],r+1);
ans+=(2*z-r-m-1)*(m+1)*(x-y);
x=y;
}
}
return ans;
}
int main(){
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<I> randGen;
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
I t;
t=readInt(1,100000,'\n');
I ns=0;
while(t--){
I ans=0;
I n;
n=readInt(1,500000,'\n');
ns+=n;
assert(ns<=500000);
I a[n];
OS(I) s;
asc(i,0,n){
if(i!=n-1){
a[i]=readInt(1,n,' ');
}else{
a[i]=readInt(1,n,'\n');
}
s.insert(a[i]);
}
assert(sz(s)==n);
I prmx[n],prmn[n],nxmx[n],nxmn[n];
V(I) v;
asc(i,0,n){
nxmx[i]=n;
if(v.empty() || a[v.back()]>a[i]){
v.pb(i);
}else{
nxmx[v.back()]=i;
v.pop_back();
i--;
}
}
clr(v);
asc(i,0,n){
nxmn[i]=n;
if(v.empty() || a[v.back()]<a[i]){
v.pb(i);
}else{
nxmn[v.back()]=i;
v.pop_back();
i--;
}
}
clr(v);
dsc(i,0,n){
prmx[i]=-1;
if(v.empty() || a[v.back()]>a[i]){
v.pb(i);
}else{
prmx[v.back()]=i;
v.pop_back();
i++;
}
}
clr(v);
dsc(i,0,n){
prmn[i]=-1;
if(v.empty() || a[v.back()]<a[i]){
v.pb(i);
}else{
prmn[v.back()]=i;
v.pop_back();
i++;
}
}
OM(P(I,I),I) mpp;
asc(i,0,n){
mpp[{prmx[i],nxmx[i]}]=i;
}
ans=cal(0,n-1,mpp,nxmn,prmn);
clr(mpp);
asc(i,0,n){
mpp[{prmn[i],nxmn[i]}]=i;
}
ans+=cal(0,n-1,mpp,nxmx,prmx);
cout<<ans<<"\n";
}
return 0;
}
Tester-2's Solution
#define ll long long
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mp make_pair
#define fo(i , n) for(ll i = 0 ; i < n ; i++)
//#include<bits/stdc++.h>
#include<iomanip>
#include<cmath>
#include<cstdio>
#include<utility>
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<stack>
ll pi = acos(-1) ;
ll z = 1000000007 ;
ll inf = 100000000000000000 ;
ll p1 = 37 ;
ll p2 = 53 ;
ll mod1 = 202976689 ;
ll mod2 = 203034253 ;
ll fact[100] ;
ll gdp(ll a , ll b){return (a - (a%b)) ;}
ll ld(ll a , ll b){if(a < 0) return -1*gdp(abs(a) , b) ; if(a%b == 0) return a ; return (a + (b - a%b)) ;} // least number >=a divisible by b
ll gd(ll a , ll b){if(a < 0) return(-1 * ld(abs(a) , b)) ; return (a - (a%b)) ;} // greatest number <= a divisible by b
ll gcd(ll a , ll b){ if(b > a) return gcd(b , a) ; if(b == 0) return a ; return gcd(b , a%b) ;}
ll e_gcd(ll a , ll b , ll &x , ll &y){ if(b > a) return e_gcd(b , a , y , x) ; if(b == 0){x = 1 ; y = 0 ; return a ;}
ll x1 , y1 ; e_gcd(b , a%b , x1 , y1) ; x = y1 ; y = (x1 - ((a/b) * y1)) ; return e_gcd(b , a%b , x1 , y1) ;}
ll power(ll a ,ll b , ll p){if(b == 0) return 1 ; ll c = power(a , b/2 , p) ; if(b%2 == 0) return ((c*c)%p) ; else return ((((c*c)%p)*a)%p) ;}
ll inverse(ll a ,ll n){return power(a , n-2 , n) ;}
ll max(ll a , ll b){if(a > b) return a ; return b ;}
ll min(ll a , ll b){if(a < b) return a ; return b ;}
ll left(ll i){return ((2*i)+1) ;}
ll right(ll i){return ((2*i) + 2) ;}
ll ncr(ll n , ll r){if(n < r) return 0 ; return ((((fact[n] * inverse(fact[r] , z)) % z) * inverse(fact[n-r] , z)) % z);}
void swap(ll&a , ll&b){ll c = a ; a = b ; b = c ; return ;}
//ios_base::sync_with_stdio(0);
//cin.tie(0); cout.tie(0);
using namespace std ;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(val) no. of elements strictly less than val
// s.find_by_order(i) itertor to ith element (0 indexed)
//__builtin_popcount(n) -> returns number of set bits in n
const int N = 2e6 + 20;
ll Tree[N] ;
void get_next_smaller(ll arr[], vector<ll>& next_smaller)
{
ll n = next_smaller.size() ;
stack<ll> s ;
s.push(n-1) ;
for(int i = n-2 ; i > 0 ; i--)
{
while(!s.empty())
{
if(arr[s.top()] > arr[i])
{
s.pop() ;
}
else
{
next_smaller[i] = s.top() ;
s.push(i) ;
break ;
}
}
}
return ;
}
void get_prev_smaller(ll arr[], vector<ll>& prev_smaller)
{
ll n = prev_smaller.size() ;
stack<ll> s ;
s.push(0) ;
for(int i = 1 ; i < n-1 ; i++)
{
while(!s.empty())
{
if(arr[s.top()] > arr[i])
s.pop() ;
else
{
prev_smaller[i] = s.top() ;
s.push(i) ;
break ;
}
}
}
return ;
}
void initialize(ll n)
{
for(int i = 0 ; i < n ; i++)
Tree[i] = 0 ;
}
void build_Tree(ll arr[] , ll par , ll l, ll r)
{
if(l == r)
{
Tree[par] = r ;
return ;
}
ll mid = (l+r)/2 ;
build_Tree(arr , left(par) , l , mid) ;
build_Tree(arr , right(par) , mid+1 , r) ;
ll val1 = arr[Tree[left(par)]] ;
ll val2 = arr[Tree[right(par)]] ;
if(val1 > val2)
Tree[par] = Tree[left(par)] ;
else
Tree[par] = Tree[right(par)] ;
return ;
}
ll query(ll arr[], ll par , ll l , ll r , ll l_ind , ll r_ind) // update type and what to return in extreme case
{
if(l_ind > r || r_ind < l)
return 0;
if(l_ind <= l && r_ind >= r)
{
return Tree[par] ;
}
ll mid = (l+r)/2 ;
ll a = query(arr, left(par) , l , mid , l_ind , r_ind) ;
ll b = query(arr, right(par) , mid+1, r , l_ind , r_ind) ;
if(arr[a] > arr[b])
return a ;
return b ;
}
void calculate_ans(ll n, vector<ll> &next_smaller, vector<ll> &prev_smaller, ll arr[], ll l, ll r, ll &ans)
{
if(l >= r)
return ;
// cout << "n = " << n << endl ;
ll mid = query(arr , 0 , 1 , n , l , r) ;
// cout << "l = " << l << " r = " << r << " mid = " << mid << endl ;
ll left_range = mid - l ;
ll right_range = r - mid ;
if(left_range <= right_range)
{
// cout << "here: " << " prev_ans = " << ans ;
ans += (-mid) * (right_range) ;
// cout << " new_ans = " << ans << endl ;
ll ind = mid-1 ;
for(int i = mid-1 ; i >= l ; i--)
{
if(arr[i] < arr[ind])
ind = i ;
ll next_ind = next_smaller[ind] ;
next_ind = min(r+1 , next_ind) ;
ll min_in_left = (next_ind - mid) ;
ll min_in_right = (r - next_ind + 1) ;
ans += (mid * min_in_left) ;
ans -= (mid * min_in_right) ;
}
}
else
{
ans += (mid * left_range) ;
ll ind = mid+1 ;
for(int i = mid+1 ; i <= r ; i++)
{
if(arr[i] < arr[ind])
ind = i ;
ll prev_ind = prev_smaller[ind] ;
prev_ind = max(prev_ind , l-1) ;
ll min_in_right = (mid - prev_ind) ;
ll min_in_left = (prev_ind - l + 1) ;
ans += (mid * min_in_left) ;
ans -= (mid * min_in_right) ;
}
}
// cout << "ans = " << ans << endl ;
// cout << endl ;
calculate_ans(n , next_smaller, prev_smaller, arr , l , mid-1 , ans) ;
calculate_ans(n , next_smaller, prev_smaller, arr , mid+1 , r , ans) ;
return ;
}
ll get_ans(ll n, ll arr[])
{
initialize(4*n) ;
build_Tree(arr , 0 , 1 , n-2) ;
vector<ll> next_smaller(n) , prev_smaller(n) ;
get_next_smaller(arr , next_smaller) ;
get_prev_smaller(arr , prev_smaller) ;
/*cout << "got indices" << endl ;
for(int i = 0 ; i < n ; i++)
cout << next_smaller[i] << ' ' ;
cout << endl ;
for(int i = 0 ; i < n ; i++)
cout << prev_smaller[i] << ' ' ;
cout << endl ;*/
ll ans = 0 ;
// cout << "before calling calculate answer" << endl ;
calculate_ans(n-2, next_smaller, prev_smaller, arr , 1 , n-2 , ans) ;
return ans ;
}
void solve()
{
ll n ;
cin >> n ;
ll arr[n+2] ;
for(int i = 1 ; i <= n ; i++)
cin >> arr[i] ;
arr[0] = arr[n+1] = 0 ;
// cout << "before calling get_ans" << endl ;
ll ans = get_ans(n+2 , arr) ;
// cout << "after calling get_ans: ans = " << ans << endl ;
for(int i = 1 ; i <= n ; i++)
arr[i] = (n+1 - arr[i]) ;
ans += get_ans(n+2 , arr) ;
cout << ans << endl ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("inputf.txt" , "r" , stdin) ;
freopen("outputf.txt" , "w" , stdout) ;
freopen("error.txt" , "w" , stderr) ;
#endif
ll t ;
cin >> t ;
//t = 1 ;
while(t--)
{
solve() ;
}
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
return 0;
}