首页 > 代码库 > hdu 5869 区间不同GCD个数(树状数组)

hdu 5869 区间不同GCD个数(树状数组)

2024-08-12 22:59:18   222人阅读

Different GCD Subarray Query

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 221    Accepted Submission(s): 58

Problem Description
This is a simple problem. The teacher gives Bob a list of problems about GCD (Greatest Common Divisor). After studying some of them, Bob thinks that GCD is so interesting. One day, he comes up with a new problem about GCD. Easy as it looks, Bob cannot figure it out himself. Now he turns to you for help, and here is the problem:
  
  Given an array a of N positive integers a1,a2,?aN−1,aN; a subarray of a is defined as a continuous interval between a1 and aN. In other words, ai,ai+1,?,aj−1,aj is a subarray of a, for 1≤i≤j≤N. For a query in the form (L,R), tell the number of different GCDs contributed by all subarrays of the interval [L,R].
  
 
Input
There are several tests, process till the end of input.
  
  For each test, the first line consists of two integers N and Q, denoting the length of the array and the number of queries, respectively. N positive integers are listed in the second line, followed by Q lines each containing two integers L,R for a query.

You can assume that 
  
    1≤N,Q≤100000 
    
   1≤ai≤1000000
 
Output
For each query, output the answer in one line.
 
Sample Input
5 31 3 4 6 93 52 51 5
 
Sample Output
666

 

 

/*hdu 5869 区间不同GCD个数(树状数组)problem:给你一组数, 然后是q个查询. 问[l,r]中所有区间GCD的值总共有多少个(不同的)solve:感觉很像线段树/树状数组. 因为有很多题都是枚举从小到大处理查询的r. 这样的话就只需要维护[1,i]的情况最开始用的set记录生成的gcd然后递推, 超时了.因为区间gcd是有单调性的.  (i-1->1)和i区间gcd是递减的.而且用RMQ可以O(1)的查询[i,j]gcd的值.如果枚举[1,i-1]感觉很麻烦.所以用二分跳过中间gcd值相同的部分,即查询与i的区间gcd值为x的最左边端点.因为要求不同的值, 这让我想到了用线段树求[l,r]中不同数的个数(忘了是哪道题了 zz)就i而言,首先找出最靠近i的位置使gcd的值为x. 然后和以前的位置作比较. 尽可能的维护这个位置靠右.假设：[3,i-1]的gcd为3,[2,i]的gcd为3.  那么在位置3上面加1.因为只要[l,i]包含这个点,那么就会有3这个值.hhh-2016-09-10 19:01:57*/#include <algorithm>#include <iostream>#include <cstdlib>#include <stdio.h>#include <cstring>#include <vector>#include <math.h>#include <queue>#include <set>#include <map>#define ll long longusing namespace std;const int maxn = 100100;int a[maxn];map<ll,int>mp;struct node{    int l,r;    int id;} p[maxn];bool tocmp(node a,node b){    if(a.r != b.r)        return a.r < b.r;    if(a.l != b.l)        return a.l < b.l;}ll Gcd(ll a,ll b){    if(b==0) return a;    else return Gcd(b,a%b);}int lowbit(int x){    return x&(-x);}ll out[maxn];ll siz[maxn];int n;void add(int x,ll val){    if(x <= 0)        return ;    while(x <= n)    {        siz[x] += val;        x += lowbit(x);    }}ll sum(int x){    if(x <=0)        return 0;    ll cnt = 0;    while(x > 0)    {        cnt += siz[x];        x -= lowbit(x);    }    return cnt;}int dp[maxn][40];int m[maxn];int RMQ(int x,int y){    int t = m[y-x+1];    return Gcd(dp[x][t],dp[y-(1<<t)+1][t]);}void iniRMQ(int n,int c[]){    m[0] = -1;    for(int i = 1; i <= n; i++)    {        m[i] = ((i&(i-1)) == 0)? m[i-1]+1:m[i-1];        dp[i][0] = c[i];    }    for(int j = 1; j <= m[n]; j++)    {        for(int i = 1; i+(1<<j)-1 <= n; i++)            dp[i][j] = Gcd(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);    }}void init(){    mp.clear();    memset(siz,0,sizeof(siz));    iniRMQ(n,a);}int main(){    int qry;    while(scanf("%d",&n) != EOF)    {        scanf("%d",&qry);        for(int i = 1; i<=n; i++)        {            scanf("%d",&a[i]);        }        init();        for(int i = 0; i < qry; i++)        {            scanf("%d",&p[i].l),scanf("%d",&p[i].r),p[i].id = i;        }        int ta = 0;        sort(p, p+qry, tocmp);        for(int i = 1; i <= n; i++)        {            int thea = a[i];            int j = i;            while(j >= 1)            {                int tmid = j;                int l = 1,r = j;                while(l <= r)                {                    int mid = (l+r) >> 1;                    if(l == r && RMQ(mid,i) == thea)                    {                        tmid = mid;                        break;                    }                    if(RMQ(mid,i) == thea)                        r = mid-1,tmid = mid;                    else                        l = mid+1;                }                if(!mp[thea])                    add(j,1);                else if(mp[thea] < j && mp[thea])                {                    add(mp[thea],-1);                    add(j,1);                }                mp[thea] = j;                j = tmid-1;                if(j >= 1) thea = RMQ(j,i);            }            while(ta < qry && p[ta].r == i)            {                out[p[ta].id] = sum(p[ta].r) - sum(p[ta].l-1);                ta++;            }        }        for(int i = 0; i < qry; i++)            printf("%I64d\n",out[i]);    }    return 0;}

　　

hdu 5869 区间不同GCD个数(树状数组)


联系
我们