【题解】洛谷&CF474F Ant colony 区间 gcd —— first_fan

在开始之前，有一些 $define$需要了解 (不然看不懂)

#define ri register int
#define ll long long
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define leaf (l==r)

虽然题目已经简化，还是来翻译下题意吧：

给你一个区间，每次问这个区间内的数字不等于区间 $gcd$ 的有多少个。

怎样？有思路了？一个裸的线段树维护 $gcd$

显然，$gcd$和题目所求的数的个数都满足区间可加性，所以说线段树搞定。

每次维护的时候，$gcd$直接加，而个数 $sum$如果判断出父子区间结点的 $gcd$相同，我们就把子节点的个数加入到父节点的个数里。

因为如果一个区间的 $gcd$同其父结点的区间 $gcd$相同，那么满足等于区间 $gcd$的数的个数一定可上传。

先把维护写好：

void pushup(ll nd)
{
    seg[nd].gcd=__gcd(seg[ls(nd)].gcd,seg[rs(nd)].gcd);
    //一句话维护 gcd
    seg[nd].sum=0;//个数归零
    if(seg[nd].gcd==seg[ls(nd)].gcd)
    {
        seg[nd].sum+=seg[ls(nd)].sum;
    }
    if(seg[nd].gcd==seg[rs(nd)].gcd)
    {
        seg[nd].sum+=seg[rs(nd)].sum;
    }//分别加
}

建树过程过于简单，此处不详讲。

void build(ll nd,ll l,ll r)
{
    seg[nd].l=l;
    seg[nd].r=r;
    if(leaf)
    {
        seg[nd].gcd=read();
        seg[nd].sum=1;
            //等于区间 gcd 的个数，叶子结点即其本身
        return ;
    }//边读边建
    ll mid=(l+r)>>1;
    build(ls(nd),l,mid);
    build(rs(nd),mid+1,r);//递归
    pushup(nd);
}

下面是线段树找区间 $gcd$模板：

ll interval_gcd(ll nd,ll l,ll r)
{
    if(seg[nd].l==l&&seg[nd].r==r)
    {
        return seg[nd].gcd;
    }//恰好塞下
    ll mid=(seg[nd].l+seg[nd].r)>>1;
    if(l>mid)
    {
        return interval_gcd(rs(nd),l,r);
    }//区间在右边
    else if(r<=mid)
    {
        return interval_gcd(ls(nd),l,r);
    }//区间在左边
    else
    {
        return __gcd(interval_gcd(ls(nd),l,mid),interval_gcd(rs(nd),mid+1,r));//拆分区间（区间跨越 mid 时）
    }
}

那么接下来就是询问环节了，几乎是裸的线段树 1 模板，只不过维护对象变成 $gcd$而已。

ll query(ll nd,ll l,ll r)
{
    if(seg[nd].l==l&&seg[nd].r==r)
    {
        return gcd==seg[nd].gcd?seg[nd].sum:0;
    }//恰
    ll mid=(seg[nd].l+seg[nd].r)>>1;
    if(l>mid)
    {
        return query(rs(nd),l,r);
    }//→
    else if(r<=mid)
    {
        return query(ls(nd),l,r);
    }//←
    else
    {
        return query(ls(nd),l,mid)+query(rs(nd),mid+1,r);
    }//跨
}

那么理下思路，我们先递归建树顺便维护，再对于询问的每个区间查询区间 $gcd$并更新 $sum$，返回输出 $sum$即可。

不得不提的一点是我们求出来的恰好是题目所求数的补集，题目问的是非 $gcd$，所以我们要用区间长减去所得 $sum$

下面是整份无注代码：

#include <bits/stdc++.h>
#define ri register ll
#define ll long long
using namespace std;
#define leaf (l==r)
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)

ll read()
{
    ll num=0;
    ll flg=1;
    char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
        {
            flg=-1;
        }
        c=getchar();
    }
    while(isdigit(c))
    {
        num=(num<<1)+(num<<3)+(c^48);
        c=getchar();
    }
    return num*flg;
}
struct segment_tree
{
    ll l,r;
    ll gcd;
    ll sum;
}seg[2003125];

ll n,m,gcd;

void pushup(ll nd)
{
    seg[nd].gcd=__gcd(seg[ls(nd)].gcd,seg[rs(nd)].gcd);
    seg[nd].sum=0;
    if(seg[nd].gcd==seg[ls(nd)].gcd)
    {
        seg[nd].sum+=seg[ls(nd)].sum;
    }
    if(seg[nd].gcd==seg[rs(nd)].gcd)
    {
        seg[nd].sum+=seg[rs(nd)].sum;
    }
}

void build(ll nd,ll l,ll r)
{
    seg[nd].l=l;
    seg[nd].r=r;
    if(leaf)
    {
        seg[nd].gcd=read();
        seg[nd].sum=1;
        return ;
    }
    ll mid=(l+r)>>1;
    build(ls(nd),l,mid);
    build(rs(nd),mid+1,r);
    pushup(nd);
}

ll interval_gcd(ll nd,ll l,ll r)
{
    if(seg[nd].l==l&&seg[nd].r==r)
    {
        return seg[nd].gcd;
    }
    ll mid=(seg[nd].l+seg[nd].r)>>1;
    if(l>mid)
    {
        return interval_gcd(rs(nd),l,r);
    }
    else if(r<=mid)
    {
        return interval_gcd(ls(nd),l,r);
    }
    else
    {
        return __gcd(interval_gcd(ls(nd),l,mid),interval_gcd(rs(nd),mid+1,r));
    }
}

ll query(ll nd,ll l,ll r)
{
    if(seg[nd].l==l&&seg[nd].r==r)
    {
        return gcd==seg[nd].gcd?seg[nd].sum:0;
    }
    ll mid=(seg[nd].l+seg[nd].r)>>1;
    if(l>mid)
    {
        return query(rs(nd),l,r);
    }
    else if(r<=mid)
    {
        return query(ls(nd),l,r);
    }
    else
    {
        return query(ls(nd),l,mid)+query(rs(nd),mid+1,r);
    }
}

int main()
{
    n=read();
    build(1,1,n);
    m=read();
    while(m--)
    {
        ll l=read();
        ll r=read();
        gcd=interval_gcd(1,l,r);
        printf("%lld\n",r+1-l-query(1,l,r));
    }
}