Please please explain the code. I am not able to figure it out


#1

#define ll long long int
const int mn = 1e5 + 5;
const ll mod = 1e9 + 7;
ll power(ll a, ll g) {ll ag = 1; while(g){if(g&1) ag = (ag%mod * a%mod)%mod; a = (a%mod * a%mod)%mod; g >>= 1;} return ag;}

ll p[mn];

void pre_compute_product_of_divisors() {
p[0] = 0; p[1] = 1;
if(p[2] != 0) return;
for(ll i = 2; i < mn; i += 1) {
if(p[i] == 0) {
p[i] = 2;
for(ll j = i+i; j < mn; j += i) {
if(p[j] == 0) p[j] = 1;
ll tmp = j;
ll cnt = 0;
while(tmp % i == 0) {
cnt += 1;
tmp /= i;
}
p[j] *= (cnt + 1);
}
}
}
for(int i = 2; i < mn; i += 1) {
p[i] = (power(i, p[i]/2)%mod * (p[i]&1 ? (ll)sqrt(i) : 1)%mod)%mod;
}
}

// comparator to sort in descending order
bool compare(pair<int, long long int> a, pair<int, long long int> g) {
if(a.first == g.first)
return a.second < g.second;
else
return a.first > g.first;
}

vector Solution::solve(vector &A, vector &B) {

pre_compute_product_of_divisors();

int n = (int)A.size();
// create arrays to store length of longest segment in which ith element is greater
long long int l[n], r[n], lr[n];
// initialize elements array equal to 1.
for(int i = 0; i < n; i += 1) {
    l[i] = r[i] = 1;
}
// find next greater element to the left of the current element
for(int i = 1; i < n; i += 1) {
    int last = i-1;
    while(last >= 0 and A[i] > A[last]) {
        l[i] += l[last];
        last -= l[last];
    }
}
// find next greater element to the right of the current element
for(int i = n-2; i >= 0; i -= 1) {
    int last = i+1;
    while(last < n and A[i] >= A[last]) {
        r[i] += r[last];
        last += r[last];
    }
}
// The number of subarrays in which current element will be the greater
for(int i = 0; i < n; i += 1) {
    lr[i] = l[i] * r[i];
}
// Sort elements in descending order according to there value
pair<int, long long int> ag[n];
for(int i = 0; i < n; i += 1) {
    ag[i] = {p[A[i]], lr[i]};
}
sort(ag, ag + n, compare);

// Take Prefix Sum of frequencies of elements
long long pre[n];
pre[0] = ag[0].second;
for(int i = 1; i < n; i += 1) {
    pre[i] = pre[i-1] + ag[i].second;
}

// do Binary search for each query
int q = (int)B.size();
vector<int> ans(q);
for(int i = 0; i < q; i += 1) {
    auto id = lower_bound(pre, pre + n, B[i]) - pre;
    ans[i] = ag[id].first;
}
// return the ans array
return ans;

}