2016 大连网络赛 hdu 5869 Different GCD Subarray Query(gcd+树状数组）★ ★

90 阅读 0 评论 60 点赞

我是靠谱客的博主冷傲小猫咪，最近开发中收集的这篇文章主要介绍2016 大连网络赛 hdu 5869 Different GCD Subarray Query(gcd+树状数组）★ ★，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：长度n的序列, m个询问区间[L, R], 问区间内的所有子段的不同GCD值有多少种.

题解：考虑固定左端点的不同GCD值，只有不超过logA种, 所以事件点只有nlogA个. 那么离线处理, 按照区间右端点排序从小到大处理询问,

用一个树状数组维护每个GCD值的最大左端点位置即可. 复杂度是O(nlogAlogn).

这份题解里有两个难点：

1、如何快速的离线化处理出固定的左端点的gcd；

2 如何用树状数组维护最大左端点，又如何求出答案？？

第一个问题：

很显然，若是平常的离散处理，时间复杂度为n^2;

for(int i = 1; i <= n; i++)
        {
            int x = num[i],y = i;
            for(int j = 0; j < gg[i-1].size(); j++)
            {
                int cc = __gcd(gg[i-1][j].first,x);
                if(x != cc)
                {
                    gg[i].push_back(make_pair(x,y));
                    x = cc,y = gg[i-1][j].second;
                }
            }
            gg[i].push_back(make_pair(x,y));
        }

这个方式我也是第一次见，将固定的左端点和得出的gcd同存在右端点，这样的确可以做到nlongA的时间离线处理。

而且这种方式存储的gcd值是从小到大的，所以不会有重存的情况出现。

主要是我不太习惯在vector 数组里用pair ,真是汗颜。。。

如何维护最大左端点呢？？

首先对查询进行右端点排序。

从左到右遍历一遍节点的gcd值。

并在树状数组里面更新相同gcd的最由端点。

#include<bits/stdc++.h>  
using namespace std;  
const int maxn=100100;  
int c[maxn];
vector< pair<int,int> > gg[maxn];
int num[maxn],vis[maxn*10],res[maxn];

struct node
{
    int l,r,id;
    bool operator <(const node&p)const
    {
        return r < p.r;
    }
} A[maxn];
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,int value)
{
    while(x < maxn)
    {
        c[x] += value;
        x += lowbit(x);
    }
}
int sum(int x)
{
    int ans = 0;
    while(x)
    {
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}
int main()
{
    int n,q;
    while(scanf("%d%d",&n,&q)!=EOF)
    {
        for(int i = 1; i <= n; i++)
        {
            scanf("%d",&num[i]);
            gg[i].clear();
        }
        memset(c,0,sizeof(c));
        for(int i = 1; i <= n; i++)
        {
            int x = num[i],y = i;
            for(int j = 0; j < gg[i-1].size(); j++)
            {
                int cc = __gcd(gg[i-1][j].first,x);
                if(x != cc)
                {
                    gg[i].push_back(make_pair(x,y));
                    x = cc,y = gg[i-1][j].second;
                }
            }
            gg[i].push_back(make_pair(x,y));
        }
        for(int i = 1; i <= q; i++)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            A[i].l = l,A[i].r = r;
            A[i].id = i;
        }
        sort(A+1,A+q+1);
        int len = 1;
        memset(vis,0,sizeof(vis));
        for(int i = 1; i <= n; i++)
        {
            for(int j = 0; j < gg[i].size(); j++)
            {
                int c1 = gg[i][j].first;
                int c2 = gg[i][j].second;
                if(vis[c1])
                    add(vis[c1],-1);
                vis[c1] = c2;
                add(c2,1);
            }
            while(A[len].r == i)
            {
                res[A[len].id] = sum(A[len].r) - sum(A[len].l - 1);
                len++;
            }
        }
        for(int i = 1; i <= q; i++)
            printf("%dn",res[i]);
    }
    return 0;
}