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. 