Solution using max query segment tree and binary search


#1

The real challenge is finding the frequency of each element. I observed that the frequency of a particular index in the result is equal to the product of its position and (number of elements-position+1)

For example, consider the array [1, 2, 3, 5, 4]

Frequency of 5 in new array G = 4*(5-4+1) = 4*2 = 8
Now consider the array from indices (0,3) and (4,4) separately as the maximum element in the original array is at index 3.

Considering array at indices (4,4)
Now, the frequency of 4 in new array G = 1*(1-1+1) = 1

Considering array at indices (0,2)
Frequency of 3 in new array G = 3*(3-3+1) = 3
The array is further split into (0,1) and (3,2) where (3,2) is invalid

Considering array at indices (0,1)
Frequency of 2 in new array G = 2*(2-2+1) = 2
Frequency of 1 in new array G = 1*(1-1+1) = 1

This approach works if the maximum element for a segment from [beg, end] is picked up each time. Segment tree can be used for this.

After the frequency of each number s obtained, the number has to be replaced by the product of its divisors. To obtain the number of divisors factorize the number and multiply them after adding 1 to the exponent of each prime factor.
If the number of divisors is odd. Then it is a perfect square, the result for it will be pow(n, number of divisors / 2)*sqrt(n) % mod
However, if the number of divisors is even. Then, the result will simply be pow(n, number of divisors / 2)*sqrt(n) % mod

Have a look at the solution.

#define N 100005
#define mod 1000000007
#define ll long long
#define fi first
#define se second
pair<ll,ll> st[4N+25];
void build(ll node, ll beg, ll end, vector& A)
{
if(beg==end)
{
st[node]={A[beg],beg};
return;
}
ll mid=beg+(end-beg)/2;
build(2
node+1,beg,mid,A);
build(2node+2,mid+1,end,A);
pair<ll,ll> p1,p2;
p1=st[2
node+1];
p2=st[2node+2];
st[node]=(p1.first>p2.first)?p1:p2;
}
pair<ll,ll> query(ll node, ll beg, ll end, ll ql, ll qr)
{
if(beg>end||beg>qr||end<ql)
return {-1,-1};
if(beg>=ql && end<=qr)
return st[node];
ll mid = beg+(end-beg)/2;
pair<ll,ll> p1 = query(2
node+1,beg,mid,ql,qr);
pair<ll,ll> p2 = query(2node+2,mid+1,end,ql,qr);
return (p1.first>p2.first)?p1:p2;
}
ll mod_power(ll b, ll e)
{
if(e==0)
return 1;
if(e==1)
return b%mod;
ll x = mod_power(b,e/2);
x=(x
x)%mod;
if(e&1)
x=(xb)%mod;
return x;
}
void get_freq(ll beg, ll end, vector& pos)
{
if(beg>end)
return;
ll n = (ll)pos.size();
pair<ll,ll> p = query(0,0,n-1,beg,end);
pos[p.se]=(p.se+1-beg)
(end-beg+1-p.se-1+beg+1);
get_freq(beg,p.se-1,pos);
get_freq(p.se+1,end,pos);
}
vector Solution::solve(vector &A, vector &B) {
ll arr[N+10];
for(ll i=0;i<N+10;i++)
arr[i]=i;
for(ll i=2;ii<=N;i++)
{
if(arr[i] < i)
continue;
for(ll j=i
i;j<=N;j+=i)
arr[j]=min(arr[j],i);
}
ll n = (ll)A.size();
build(0,0,n-1,A);
vector<pair<ll,ll>> vp;
vector pos(n);
get_freq(0,n-1,pos);
for(ll i=0;i<n;i++)
vp.push_back({A[i],pos[i]});
for(ll i=0;i<n;i++)
{
ll x = (ll)vp[i].fi;
map<ll,ll> mp;
while(x!=1)
{
++mp[arr[x]];
x/=arr[x];
}
ll val=1;
for(auto it: mp)
val*=(it.se+1);
ll ans = mod_power(vp[i].fi,val/2);
if(val%2)
ans=(ans*(ll)(sqrt(A[i])))%mod;
vp[i].fi=ans;
}
sort(vp.rbegin(),vp.rend());
ll sum = 0;
vector search;
for(ll i=0;i<n;i++)
{
sum+=vp[i].second;
search.push_back(sum);
}
vector ans;
for(ll i=0;i<(ll)B.size();i++)
{
ll pos=lower_bound(search.begin(),search.end(),B[i])-search.begin();
ans.push_back((int)vp[pos].first);
}
return ans;
}