程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces Round #271 (Div. 2) F題 Ant colony（線段樹）

Codeforces Round #271 (Div. 2) F題 Ant colony（線段樹）

編輯：C++入門知識

Codeforces Round #271 (Div. 2) F題 Ant colony（線段樹）

由題意可知，最後可以留下來的一定是區間最小gcd。那就轉化成了該區間內與區間最小gcd數相等的個數。區間最小gcd一定小於等於區間最小值，所以只要先判斷最小值是否是最小gcd。若是的話，就求出最小值的個數，然後用r-l+1-個數即可。

對於以上信息，可以用線段樹來維護。分別維護區間gcd，區間最小值以及區間最小值的個數。

代碼如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 

using namespace std;
#define LL __int64
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
const int INF=0x3f3f3f3f;
const int MAXN=100000;
int minv[MAXN<<2], gcd[MAXN<<2], num[MAXN<<2], q_minv, q_gcd, q_num;
int getgcd(int a, int b)
{
    return a==0?b:getgcd(b%a,a);
}
void PushUp(int rt)
{
    minv[rt]=min(minv[rt<<1],minv[rt<<1|1]);
    gcd[rt]=getgcd(gcd[rt<<1],gcd[rt<<1|1]);
    if(minv[rt<<1]==minv[rt<<1|1])
        num[rt]=num[rt<<1]+num[rt<<1|1];
    else if(minv[rt<<1]>minv[rt<<1|1])
        num[rt]=num[rt<<1|1];
    else
        num[rt]=num[rt<<1];
}
void build(int l, int r, int rt)
{
    if(l==r)
    {
        scanf(%d,&minv[rt]);
        num[rt]=1;
        gcd[rt]=minv[rt];
        return ;
    }
    int mid=l+r>>1;
    build(lson);
    build(rson);
    PushUp(rt);
}
void query(int ll, int rr, int l, int r, int rt)
{
    if(ll<=l&&rr>=r)
    {
        q_gcd=getgcd(q_gcd,gcd[rt]);
        if(minv[rt]==q_minv)
        {
            q_num+=num[rt];
        }
        else if(minv[rt]>1;
    if(ll<=mid) query(ll, rr, lson);
    if(rr>mid) query(ll,rr,rson);
}
int main()
{
    int n, m, i, l, r;
    scanf(%d,&n);
    build(1, n, 1);
    /*for(i=1;i<=9;i++)
    {
        printf(%d %d %d
,minv[i], gcd[i], num[i]);
    }*/
    scanf(%d,&m);
    while(m--)
    {
        scanf(%d%d,&l,&r);
        q_minv=INF;
        q_gcd=0;
        q_num=0;
        query(l,r,1,n,1);
        if(q_gcd==q_minv)
        {
            printf(%d
,r-l+1-q_num);
        }
        else
        {
            printf(%d
,r-l+1);
        }
    }
    return 0;
}