Codeforces Round #271 (Div. 2) F题 Ant colony（线段树） - c++编程基础

TOP

Codeforces Round #271 (Div. 2) F题 Ant colony（线段树）

2015-07-20 17:31:58 来源: 作者: 【大中小】浏览:2次

Tags：Codeforces Round #271 Div. 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; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：Gas Station [leetcode] 的两种解..	下一篇：C++中的函数隐藏

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: