2016 大連網賽---Different GCD Subarray Query(GCD離散+樹狀數組)，樹狀數組離散化

2016 大連網賽---Different GCD Subarray Query(GCD離散+樹狀數組)，樹狀數組離散化

題目鏈接

http://acm.split.hdu.edu.cn/showproblem.php?pid=5869

 

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 3 1 3 4 6 9 3 5 2 5 1 5   Sample Output 6 6 6   Source 2016 ACM/ICPC Asia Regional Dalian Online   Recommend wange2014   |   We have carefully selected several similar problems for you:  5877 5876 5874 5873 5872    題意：輸入N和Q，表示有N個數的一個序列，Q次詢問，每次輸入 l 和 r 表示一個區間，求這個區間不同的最大公倍數的個數（由這個區間的子區間得到）；   思路：對數列進行GCD離散處理（~我也是才知道還有這樣的離散~）         

for(int i=1;i<=N;i++)
        {
            int tot=a[i],pos=i;
            for(int j=0;j<v[i-1].size();j++)
            {
                int  r=__gcd(a[i],v[i-1][j].first);
                if(tot!=r)
                {
                   v[i].push_back(make_pair(tot,pos));
                   tot=r;  pos=v[i-1][j].second;
                }
            }
            v[i].push_back(make_pair(tot,pos));
        }

       然後對Q次詢問離線處理，先輸入Q次詢問的區間，然後按右端點從小到大排序，i從1~N循環，當i==node[len].r  則 ans[node[len].id]=Sum(i)-Sum(node[len].l-1) ; 可以方便快速的用樹狀數組處理；   代碼如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
using namespace std;
int a[100005];
int c[1000005];
int vis[1000005];
int sum[100005];
struct Node
{
    int l,r;
    int id;
}node[100005];
bool cmp(const Node s1,const Node s2)
{
    return s1.r<s2.r;
}
vector<pair<int,int> > v[100005];

int __gcd(int x,int y)
{
    int r=x%y;
    x=y;
    y=r;
    if(r==0) return x;
    return __gcd(x,y);
}
int Lowbit(int t)
{
    return t&(t^(t-1));
}
int Sum(int x)
{
    int sum = 0;
    while(x > 0)
    {
        sum += c[x];
        x -= Lowbit(x);
    }
    return sum;
}
void add(int li,int t)
{
    while(li<=1000005)
    {
        c[li]+=t;
        li=li+Lowbit(li);
    }
}
int main()
{
    int N,Q;
    while(scanf("%d%d",&N,&Q)!=EOF)
    {
        for(int i=1;i<=N;i++) scanf("%d",&a[i]);
        for(int i=1;i<=N;i++)
        {
            int tot=a[i],pos=i;
            for(int j=0;j<v[i-1].size();j++)
            {
                int  r=__gcd(a[i],v[i-1][j].first);
                if(tot!=r)
                {
                   v[i].push_back(make_pair(tot,pos));
                   tot=r;  pos=v[i-1][j].second;
                }
            }
            v[i].push_back(make_pair(tot,pos));
        }

        for(int i=0;i<Q;i++)
            scanf("%d%d",&node[i].l,&node[i].r),node[i].id=i;
        sort(node,node+Q,cmp);
        memset(c,0,sizeof(c));
        memset(vis,0,sizeof(vis));
        int len=0;
        for(int i=1;i<=N;i++)
        {
            for(int j=0;j<v[i].size();j++)
            {
                int s1=v[i][j].first;
                int s2=v[i][j].second;
                if(vis[s1]){
                    add(vis[s1],-1);
                }
                vis[s1]=s2;
                add(s2,1);
            }
            while(node[len].r==i)
            {
                sum[node[len].id]=Sum(i)-Sum(node[len].l-1);
                len++;
            }
        }
        for(int i=0;i<Q;i++)
            printf("%d\n",sum[i]);
        for(int i=0;i<=N;i++)
            v[i].clear();
    }
    return 0;
}