A1016054 - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Abdel-Aziz Mostafa
Tester: Samarth Gupta
Editorialist: Taranpreet Singh

DIFFICULTY

Medium

PREREQUISITES

Observation, Fenwick Tree

PROBLEM

Given an array A with N distinct integers, a subarray [L, R] is called Tsetso subarray if A_L \cdot A_R = max(A_L, A_{L+1} \ldots A_{R-1}, A_R)

Answer queries of the form. Given interval [L, R], count the number of Tsetso subarrays completely inside the query range.

QUICK EXPLANATION

  • The number of Tsetso subarrays is approximately N*log_2(N).
  • For element A_p, consider all intervals [l, r] such that l \leq p \leq r and A_p is the maximum element in subarray [l, r]. A_l and A_r must be factor of A_p in order to get a Tsetso subarray.
  • Iterate over elements l \leq le \leq p on one side (say left), then we can check if A_p / A_{le} is present in range [p, r]. If it is present at position ri such that p \leq ri \leq r, then subarray [le, ri] is a Tsetso subarray.
  • After finding all subarrays, we just need to count the number of subarrays completely inside each query ranges, which can be done by sorting intervals by the right end and answering queries offline.

EXPLANATION

Since all elements are distinct, we can see that in an interval, no two elements are maximum at the same time. Let’s say the maximum of the array is present at position p. Then all subarrays [L, R] having L \leq p \leq R shall have it’s maximum value A_p. So all Tsetso subarrays would have A_L and A_R as factors of A_p. This, combined with the fact that all elements in the array are distinct, would suggest that number of subarrays would be quite less than N^2.

Let’s try finding all Tsetso subarrays.

Finding all Tsetso subarrays

Considering subarray [L, R] where A_p is the maximum in range [L, R]. Then all subarrays L \leq p \leq R have A_p as maximum. If we fix A_L, A_R = A_p/A_L must hold. Hence, let’s iterate i from L to p. We know the value x = A_p / A_i. If value x is present at position j where p \leq q \leq R, then subarray [i, j] is a Tsetso subarray.

Hence, we can find all Tsetso subarrays with A_p as maximum. Now we only need to consider subarrays in the range [L, p-1] and [p+1, R], which are similar sub-problems.

Since we needed to do O(N) work (Consider ascending or descending array A) and we got two smaller sub-problems, this can lead to O(N^2) time in the worst case to find all subarrays. But we can improve

Number of subarrays

Earlier, we iterated on one side. Now, let’s choose to iterate on the smaller side. For example, if we are considering range [3, 10] and we have p = 8, then let’s iterate on the right side fixing A_R and use map/binary search to check if A_p/A_R is present in the range [L, p].

While this may seem a small thing, it actually reduces time complexity to generate all subarrays from O(N^2) to O(N*log(N)).

Let’s say we start at interval [L, R] and the maximum element is at position p. We do only min(R-p, p-L) iterations, and got two subproblems [L, p-1] and [p+1, R]. The worst-case happens when p is roughly in middle, leading to $(R-L)/2 iterations and two subproblems of size N/2.

We can write the worst case recurrence as T(N) = 2*T(N/2) + O(N) which leads to O(N*log(N)) time.

Also, since in each iteration one subarray is being considered, the number of Tsetso subarrays is roughly N*log_2(N).

We can use RMQ, or Segment Tree or even sorting to process elements in decreasing order and finding for each element A_p, the range [L, R] where A_p is maximum and finding all Tsetso subarrays.

Answer queries

Now we have all Tsetso subarrays in a single list. We need to answer the number of subarrays present completely inside the query range. This is somewhat well known, but I’d reiterate in brief.

Let’s sort all the arrays, and all the queries by the right end in non-decreasing order. Before answering q-th query with range [L, R], add all subarrays with right end \leq R into a DS. Now, we only need to count the number of subarrays present in DS, which have left end \geq L.

We can see that subarrays having the right end beyond R wouldn’t be added to DS, and the left end is taken care of by counting only numbers having the left end \geq L.

One popular choice for DS would be Fenwick Tree, where when adding subarray [l, r] to DS, we increment position l by 1. When answering a query for the range [L, R], we can simply query the sum of range [L, R].

Since each subarray is added to DS only once, and all queries need to be processed only once, this solution works in O(N*log^2(N) + Q*log(N)) (Sorting and Fenwick Tree operations).

TIME COMPLEXITY

SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>
#define ll long long
#define S second
#define F first
#define Tsetso ios_base::sync_with_stdio(0) ; cin.tie(0) ;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pair < int , int > , null_type,less<pair < int , int > >, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
const ll  N = 5e5+50 , mod = 1e9+7, inf = 2e18 , length = 25;
ll st[N][30], a[N],Log[N] , n , q;
map < ll , int > pos;
ordered_set ost;
void pre()
{
    Log[1] = 0;
    for (int i = 2; i <= n; i++)
        Log[i] = Log[i/2] + 1;
    for (int i = 0; i < n; i++)
        st[i][0] = a[i];
    for (int j = 1; j <= 25; j++)
        for (int i = 0; i + (1 << j) <= n; i++)
            st[i][j] = max(st[i][j-1], st[i + (1 << (j - 1))][j - 1]);
}
ll calcmx( int L , int R )
{
    if ( L > R)
        return 0;
    int j = Log[R - L + 1];
    return max(st[L][j], st[R - (1 << j) + 1][j]);
}
vector < pair < int , int > > ranges;
void solve ()
{
    for ( int idx = 0 ; idx < n ; idx++) {
        int l = idx , r = idx ;
        int start = 0  , end = l-1;
        while(start <= end)
        {
            int mid = (start + end) >> 1 ;
            if ( calcmx(mid,idx-1) < a[idx])
                end = mid-1,l = mid;
            else
                start = mid+1;
        }
        start = idx+1 , end = n-1;
        while (start <= end)
        {
            int mid = (start + end) >> 1 ;
            if ( calcmx(idx+1,mid) < a[idx])
                start = mid+1,r = mid;
            else
                end = mid-1;
        }
        if (l == r) {
            if (a[idx] <= 1)
                ranges.push_back({l + 1, r + 1});
            continue;
        }
        int left = idx - l, right = r - idx;
        if (left <= right) {
            for (int i = l; i <= idx; i++) {
                if (a[i] == 0 || (a[i] && a[idx] % a[i]))
                    continue;
                ll num = a[idx] / a[i];
                if (pos.find(num) == pos.end() || pos[num] < idx || pos[num] > r)
                    continue;
                ranges.push_back({i + 1, pos[num] + 1});
            }
        } else {
            for (int i = idx; i <= r; i++) {
                if (a[i] == 0 || (a[i] && a[idx] % a[i]))
                    continue;
                ll num = a[idx] / a[i];
                if (pos.find(num) == pos.end() || pos[num] < l || pos[num] > idx)
                    continue;
                ranges.push_back({pos[num] + 1, i + 1});
            }
        }
    }
}
int main() {
    Tsetso
    int t;
    cin >> t;
    while (t--) {
        ranges.clear();
        pos.clear();
        ost.clear();
        cin >> n >> q;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            assert(pos.find(a[i]) == pos.end());
            pos[a[i]] = i;
        }
        pre();
        solve();
        vector < pair <pair < int , int > , int > > query;
        for ( int qq = 1 ; qq <= q ; qq++) {
            int l ,r ;
            cin >> l >> r ;
            query.push_back({{l,r},qq});
        }
        sort(query.begin(),query.end());
        sort(ranges.begin(),ranges.end());
        vector < int > ans(q+1);
        while (!query.empty())
        {
            int l = query.back().F.F , r = query.back().F.S;
            int idx = query.back().S;
            query.pop_back();
            while(!ranges.empty() && ranges.back().first >= l)
            {
                ost.insert({ranges.back().S,ost.size()});
                ranges.pop_back();
            }
            ans[idx] = ost.order_of_key({r,1e9});
        }
        for ( int i = 1 ; i <= q ; i++)
                cout << ans[i] << '\n';
    }
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;

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;
            }
            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;
}
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');
}
string readStringLn(int l, int r) {
    return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
    return readString(l,r,' ');
}
 
void readEOF(){
    assert(getchar()==EOF);
}
vector<pair<int, int>> rng;
void solve(vector<long long> &vec, int l, int r){ // number of Tsetso subarrays in range [l, r]
    if(l == r){
        if(vec[l] == 1)
            rng.push_back({l, r});
        return;
    }
    int mid = (l + r)/2;
    solve(vec, l, mid);
    solve(vec, mid+1, r);
    // [l, mid] and [mid + 1, r], assuming maximum is in left side
    map<long long, int> mp;
    int i = mid, j = mid;
    long long mx = 0;
    while(i >= l){
        if(mx < vec[i])
            mx = vec[i];
        while(j <= r - 1 && vec[j + 1] < mx)
            j++, mp[vec[j]] = j;
        if(mx%vec[i] == 0 && mp.find(mx/vec[i]) != mp.end())
            rng.push_back({i, mp[mx/vec[i]]});
        i--;
    }
    mp.clear();
    // assume maximum is in right side
    i = mid + 1, j = mid + 1;
    mx = 0;
    while(j <= r){
        if(mx < vec[j])
            mx = vec[j];
        while(i >= l + 1 && vec[i - 1] < mx)
            i--, mp[vec[i]] = i;
        if(mx%vec[j] == 0 && mp.find(mx/vec[j]) != mp.end())
            rng.push_back({mp[mx/vec[j]], j});
        j++;
    }
}
// BIT update
void update(int bit[], int idx, int m, int val){
    while(idx <= m)
        bit[idx] += val, idx += (idx&-idx);
}
int query(int bit[], int idx){
    int sum = 0;
    while(idx)
        sum += bit[idx], idx -= (idx&-idx);
    return sum;
}
// Query Part
// https://www.geeksforgeeks.org/number-elements-less-equal-given-number-given-subarray/
vector<int> solve(vector<pair<int, int>> arr, vector<pair<int, pair<int, int>>> queries, int m){
    int q = queries.size();
    vector<int> ans(q);
    sort(arr.begin(), arr.end());
    sort(queries.begin(), queries.end());
    int bit[m + 1] = {0};
    int cur = 0;
    for(int i = 0 ; i < q ; i++){
        while(cur < m && arr[cur].first <= queries[i].first)
            update(bit, arr[cur].second + 1, m, 1), cur++;
        ans[queries[i].second.second] = query(bit, m) - query(bit, queries[i].second.first);
    }
    return ans;
}
int main() {
    // your code goes here
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    int sumn = 0, sumq = 0;
    while(t--){
        int n, q;
        cin >> n >> q;
        sumn += n, sumq += q;
        assert(sumn <= 5e5);
        assert(sumq <= 1e6);
        vector<long long> vec(n);
        for(int i = 0; i < n ; i++){
            cin >> vec[i];
        }
        // distinct elements check
        vector<long long> nums = vec;
        sort(nums.begin(), nums.end());
        nums.resize(unique(nums.begin(), nums.end()) - nums.begin());
        assert(nums.size() == n);
        
        rng.clear(); // stores the ranges
        solve(vec, 0, n - 1);
        sort(rng.begin(), rng.end());
        vector<pair<int, int>> right;
        for(int i = 0; i < rng.size() ; i++)
            right.push_back({rng[i].second, i});
        int m = rng.size();
        vector<pair<int, pair<int, int>>> queries;
        for(int i = 0; i < q ; i++){
            int l, r;
            cin >> l >> r;
            l--, r--;
            pair<int, int> p = {l, 0};
            int idx = lower_bound(rng.begin(), rng.end(), p) - rng.begin();
            // Search for elements <= r in range [idx, m - 1] in array right, can be done using BIT
            queries.push_back({r, {idx, i}});
        }
        vector<int> ans = solve(right, queries, m);
        for(int i = 0 ; i < q ; i++)
            cout << ans[i] << '\n';
    }
    readEOF();
    return 0;
}
Editorialist's Solution
#include<bits/stdc++.h>
#define ll long long
#define S second
#define F first
#define Tsetso ios_base::sync_with_stdio(0) ; cin.tie(0) ;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pair < int , int > , null_type,less<pair < int , int > >, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
const ll  N = 5e5+50 , mod = 1e9+7, inf = 2e18 , length = 25;
ll st[N][30], a[N],Log[N] , n , q;
map < ll , int > pos;
ordered_set ost;
void pre()
{
    Log[1] = 0;
    for (int i = 2; i <= n; i++)
        Log[i] = Log[i/2] + 1;
    for (int i = 0; i < n; i++)
        st[i][0] = a[i];
    for (int j = 1; j <= 25; j++)
        for (int i = 0; i + (1 << j) <= n; i++)
            st[i][j] = max(st[i][j-1], st[i + (1 << (j - 1))][j - 1]);
}
ll calcmx( int L , int R )
{
    if ( L > R)
        return 0;
    int j = Log[R - L + 1];
    return max(st[L][j], st[R - (1 << j) + 1][j]);
}
vector < pair < int , int > > ranges;
void solve ()
{
    for ( int idx = 0 ; idx < n ; idx++) {
        int l = idx , r = idx ;
        int start = 0  , end = l-1;
        while(start <= end)
        {
            int mid = (start + end) >> 1 ;
            if ( calcmx(mid,idx-1) < a[idx])
                end = mid-1,l = mid;
            else
                start = mid+1;
        }
        start = idx+1 , end = n-1;
        while (start <= end)
        {
            int mid = (start + end) >> 1 ;
            if ( calcmx(idx+1,mid) < a[idx])
                start = mid+1,r = mid;
            else
                end = mid-1;
        }
        if (l == r) {
            if (a[idx] <= 1)
                ranges.push_back({l + 1, r + 1});
            continue;
        }
        int left = idx - l, right = r - idx;
        if (left <= right) {
            for (int i = l; i <= idx; i++) {
                if (a[i] == 0 || (a[i] && a[idx] % a[i]))
                    continue;
                ll num = a[idx] / a[i];
                if (pos.find(num) == pos.end() || pos[num] < idx || pos[num] > r)
                    continue;
                ranges.push_back({i + 1, pos[num] + 1});
            }
        } else {
            for (int i = idx; i <= r; i++) {
                if (a[i] == 0 || (a[i] && a[idx] % a[i]))
                    continue;
                ll num = a[idx] / a[i];
                if (pos.find(num) == pos.end() || pos[num] < l || pos[num] > idx)
                    continue;
                ranges.push_back({pos[num] + 1, i + 1});
            }
        }
    }
}
int main() {
    Tsetso
    int t;
    cin >> t;
    while (t--) {
        ranges.clear();
        pos.clear();
        ost.clear();
        cin >> n >> q;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            assert(pos.find(a[i]) == pos.end());
            pos[a[i]] = i;
        }
        pre();
        solve();
        vector < pair <pair < int , int > , int > > query;
        for ( int qq = 1 ; qq <= q ; qq++) {
            int l ,r ;
            cin >> l >> r ;
            query.push_back({{l,r},qq});
        }
        sort(query.begin(),query.end());
        sort(ranges.begin(),ranges.end());
        vector < int > ans(q+1);
        while (!query.empty())
        {
            int l = query.back().F.F , r = query.back().F.S;
            int idx = query.back().S;
            query.pop_back();
            while(!ranges.empty() && ranges.back().first >= l)
            {
                ost.insert({ranges.back().S,ost.size()});
                ranges.pop_back();
            }
            ans[idx] = ost.order_of_key({r,1e9});
        }
        for ( int i = 1 ; i <= q ; i++)
                cout << ans[i] << '\n';
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

3 Likes

I came up with recursive a solution of complexity O(N * log(N) + Q * N) but sadly got TLE.
I made a sparse table to get max element from the given range and its position in O(1) time(as each element was distinct so i stored it hashmap to get its position), its construction took O(N * log(N)) time.
My approach was basically to do this recursively:

Count(left, right):

  1. Get max element in left,right and position of that element, say maxPos
  2. let i = maxPos…left, if a[i] is divisible by max element and maxPos >= pos[max / a[i]] <= right, then answer++
  3. Call count(left, maxPos - 1) and count(maxPos + 1, right), it is sort of like quick sort array split.

Code: Solution: 51166920 | CodeChef

I think python is quite slow when it comes to recursion or multi-dimensional arrays. I suppose someone good in python might be able to comment.

Also, there’s a file with RE as well, so some other issue is there as well.

Also, I believe your solution is O(N*Q*log(N)) which is bound to TLE (unless I misunderstood). testo function takes O(N*log(N)) time for each query.

My bad, solution is indeed O(NQlog(N)), in worst case it will go to O(N² * Q), when elements are in sorted order, which is why I am getting TLE.
As far as the RE problem, it is due to max recursion limit, I did think of this and submitted a solution with queue instead of recursion as a result of which RE was gone and TLE remained, link to that: Solution: 51169211 | CodeChef

Damnnn. Just putting it here, the solution seems to be inspired by small to large merging in trees. Check that out too. Here. Great problem!

1 Like

Can somebody explain why only (5,5) is allowed as answer in input test case? Not other (i,i).