首页 / HTML / CodeforcesRound#271(Div.2)F题Antcolony（线段树）_html/css_WEB-ITnose

CodeforcesRound#271(Div.2)F题Antcolony（线段树）_html/css_WEB-ITnose

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了CodeforcesRound#271(Div.2)F题Antcolony（线段树）_html/css_WEB-ITnose，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2055字，纯文字阅读大概需要3分钟。

内容图文

题目地址：http://codeforces.com/contest/474/problem/F

由题意可知，最后可以留下来的一定是区间最小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|1const 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]<q_minv)        {            q_num=num[rt];            q_minv=minv[rt];        }        return ;    }    int mid=l+r>>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\n",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\n",r-l+1-q_num);        }        else        {            printf("%d\n",r-l+1);        }    }    return 0;}

内容总结

以上是互联网集市为您收集整理的CodeforcesRound#271(Div.2)F题Antcolony（线段树）_html/css_WEB-ITnose全部内容，希望文章能够帮你解决CodeforcesRound#271(Div.2)F题Antcolony（线段树）_html/css_WEB-ITnose所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/398737.html

来源：【匿名】