【CODEFORECES】F.Ant colony

F.Ant colony
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
out put
スタンダードアウト
Mole is hunry again.He found one ant colony、consisting of n ants,orded in a row.Each ant i (1̵≦̵i𔎅≦𔎅n)has a streength si.
In order to make his dinner more interesting,Mole organizes a version of≪Hunger Games≫for the ants.He choses 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 ファイト、ant i gets one battle point only if シンプル 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 fred only if vi̵=̵r-̵l,or in other words only if it took a point in everfight it participted.After that,Mole eats the ret of the ants.Note there can be manbe fred or novene.
In order to chose the best sequence,Mole gives you t segments [li,̵り] 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 s 1,̵s2,̵…,𔎅sn (1̵≦̵si≦𔎅109)、the streengths of the ants.
The third line contains one integer t (1̵≦̵t≦𔎅105)、the number of test cases.
Each of the next t LINE contains two integers li. and ri (1̵≦̵li𔎅≦𔎅り≦𔎅n)、describing one query.
Output
Print to the standard output t LINE.The i-th line contains number of ants that Mole eats from the segment [li,̵り]
Sample test(s)
input

5
1 3 2 4 2
4
1 5
2 5
3 5
4 5

out put

4
4
1
1

ノート
In the first test battle points for each ant are v(8201)=𔎅[4,̵0,𔎅2,̵0,𔎅2]ソナントnumber 1 is freed.Mole eats the ants 2, 3, 4, 5.
In the second test case battle points are v(8201)=̵[0,̵2,̵0,̵2]ソノANt is freed and all of them are eaten by Mole.
In the third test case battle points are v̵=̵[2,̵0,̵2]ソナナナナナナナナナソニックnumber 3 and 5 are freed.Mole eats only the ant 4.
In the fourth test case battle points are v̵=̵[0,̵1]ソナンパ 5 is freed.Mole eats the ant 4.
この問題は難しくないです.一つの区間のGCDが区間の最小値に等しくなければ、この区間の全部の数は食べられます.(この区間のGCDでない限り、各数は他の全ての数で割り切れるわけではないので)、この区間のGCDがこの区間の最小値に等しいなら、この最小値は放しられ、食べ残します.そこで私たちは線分樹で各区間のGCD、最小値と最小値の個数を維持することができます.検索する時は徐々に進めばいいです.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;

struct tree
{
    int mins,l,r,sum,k;
};

int s[100005],l,r,n,t,x,mins,sum;
struct tree d[300005];

int gcd(int a,int b)
{
    if (b==0) return a;
    else return gcd(b,a%b);
}

void buildtree(int k,int l,int r)
{
    d[k].l=l; d[k].r=r;
    if (l==r)
    {
        d[k].k=s[l];
        d[k].mins=s[l];
        d[k].sum=1;
    }
    else
    {
        buildtree(k*2,l,(l+r)/2);
        buildtree(k*2+1,(l+r)/2+1,r);
        d[k].k=gcd(d[k*2].k,d[k*2+1].k);
        if (d[k*2].mins==d[k*2+1].mins)
        {
            d[k].mins=d[k*2].mins;
            d[k].sum=d[k*2].sum+d[k*2+1].sum;
        }
        else if (d[k*2].mins<d[k*2+1].mins)
        {
            d[k].mins=d[k*2].mins;
            d[k].sum=d[k*2].sum;
        }
        else
        {
            d[k].mins=d[k*2+1].mins;
            d[k].sum=d[k*2+1].sum;
        }
    }
}

void countk(int k,int l,int r)
{
    int t=(d[k].l+d[k].r)/2;
    if (d[k].l==l && d[k].r==r)
    {
        x=gcd(d[k].k,x);
        if (mins==d[k].mins) sum+=d[k].sum;
        else if (mins>d[k].mins)
        {
            mins=d[k].mins;
            sum=d[k].sum;
        }
    }
    else if (r<=t) countk(k*2,l,r);
    else if (l>=t+1) countk(k*2+1,l,r);
    else
    {
        countk(k*2,l,t);
        countk(k*2+1,t+1,r);
    }
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&s[i]);
    scanf("%d",&t);
    buildtree(1,1,n);
    for (int i=1;i<=t;i++)
    {
        scanf("%d%d",&l,&r);
        x=s[l]; sum=0;
        mins=s[l];
        countk(1,l,r);
        if (x==mins) printf("%d
",r-l+1-sum);
        else printf("%d
",r-l+1);
    }
    return 0;
}