F. Ant colony
Mole is hungry again. He found one ant colony, consisting of n ants, ordered in a row. Each ant i (1 ≤ i ≤ n) has a strength si.
In order to make his dinner more interesting, Mole organizes a version of «Hunger Games» for the ants. He chooses two numbers l andr (1 ≤ l ≤ r ≤ n) and each pair of ants with indices between l and r (inclusively) will fight. When two ants i and j fight, ant i gets one battle point only if si divides sj (also, ant j gets one battle point only if sj divides si).
After all fights have been finished, Mole makes the ranking. An ant i, with vi battle points obtained, is going to be freed only if vi = r - l, or in other words only if it took a point in every fight it participated. After that, Mole eats the rest of the ants. Note that there can be many ants freed or even none.
In order to choose the best sequence, Mole gives you t segments [li, ri] and asks for each of them how many ants is he going to eat if those ants fight.
Input
The first line contains one integer n (1 ≤ n ≤ 105), the size of the ant colony.
The second line contains n integers s1, s2, ..., sn (1 ≤ si ≤ 109), the strengths of the ants.
The third line contains one integer t (1 ≤ t ≤ 105), the number of test cases.
Each of the next t lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n), describing one query.
Output
Print to the standard output t lines. The i-th line contains number of ants that Mole eats from the segment [li, ri].
Examples
input
5 1 3 2 4 2 4 1 5 2 5 3 5 4 5
output
4 4 1 1
Note
In the first test battle points for each ant are v = [4, 0, 2, 0, 2], so ant number 1 is freed. Mole eats the ants 2, 3, 4, 5.
In the second test case battle points are v = [0, 2, 0, 2], so no ant is freed and all of them are eaten by Mole.
In the third test case battle points are v = [2, 0, 2], so ants number 3 and 5 are freed. Mole eats only the ant 4.
In the fourth test case battle points are v = [0, 1], so ant number 5 is freed. Mole eats the ant 4.
----------------------------------------------------------EDITORIAL-------------------------------------------------------------
For each subsequence [L, R] we must find how many queens we have. A value is "queen" only if is the GCD of (sL, sL + 1, ..., sR). Also, we must notice that the GCD of (sL, sL + 1, ..., sR) can be only the minimum value from (sL, sL + 1, ..., sR). So for each query we search in a data structure (a segment tree or a RMQ) the minimum value and the GCD of (sL, sL + 1, ..., sR) and if these two values are equal then we output the answer R - L + 1 - nrValues, where nrValues is the number of values in the subsequence equal to the GCD and the minimum value. The complexity of this solution is O(n·log(n)·log(valMax) + t·log(n)·log(valMax)), where valMax is the maximum value of si.
in this implementation main thing was how to find no of occurance of a number in the range L to R
i used a awesome approach to do that ,
sort all numbers in a vector with pair of there position in the array ,pair<val,pos>
now suppose we need to find number of occurance of number x in the range L1, to L2
this will be (lower_bound(v.begin(),v.end(),pair<x,L2>)-v.begin())-(lower_bound(v.begin(),v.end(),pair<x,L1>)-v.begin())
let us see a example to check this
sulppose we have array 1,2,3,2,5,2,7,2,3,2
its sorted vector pair<> will be
(1,1)
(2,2)
(2,4)
(2,6)
(2,8)
(2,10)
(3,3)
(3,9)
(5,5)
(7,7)
now suppose we search for no of occurance of in the range 1,5
=((lower_bound(all(v),<2,5+1> - v.begin()) -- (lower_bound(all(v),<2,1> - v.begin())
=2
---------------------------------------------------code------------------------------------------------------------------------
#include<bits/stdc++.h>
typedef long long int lli;
lli seg[1000000];
using namespace std;
vector<pair<lli,int> > v;
lli arr[1000000];
void build(int index,int start,int end)
{
// cout<<" index "<<start<<" "<<end<<endl;
if(start>end)
return ;
if(start==end)
{
seg[index]=arr[start];
// cout<<" index "<<start<<" "<<end<<" val "<<arr[start]<<endl;
return ;
}
int mid=(start+end)/2;
build(2*index,start,mid);
build(2*index+1,mid+1,end);
seg[index]=__gcd(seg[2*index],seg[2*index+1]);
//cout<<" index "<<start<<" "<<end<<" val "<<seg[index]<<endl;
}
lli query(int index,int start,int end,int qs,int qe)
{
//cout<<" index "<<start<<" "<<end<<endl;
if(start>end || start>qe || end<qs) return 0;
else if(start>=qs && end<=qe)
{
// cout<<"hh";
return seg[index];
}
lli q1=query(2*index,start,(start+end)/2,qs,qe);
lli q2=query(2*index+1,(start+end)/2+1,end,qs,qe);
return __gcd(q1,q2);
}
// function to calc times of occurance
int occurance(int index,lli val)
{
pair<lli,int> pp;
pp=make_pair(val,index);
int count=lower_bound(v.begin(),v.end(),pp)-v.begin();
return count;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
scanf("%lld",&arr[i]);
v.push_back({arr[i],i});
}
build(1,0,n-1);
sort(v.begin(),v.end());
int q;
scanf("%d",&q);
while(q--)
{
int l,r;
cin>>l>>r;
l--;
r--;
lli val=query(1,0,n-1,l,r);
cout<<(r-l+1)-(occurance(r+1,val)-occurance(l,val))<<endl;
}
return 0;
}
No comments:
Post a Comment