hdu 4630 树状数组

思路：这题的处理方式和hdu4358有点像。我们用一个pre[x]表示约数x的倍数上次出现的位置，将查询按区间的右节点升序排序。num[i]的约数为j，如果pre[j]为0，就将pre[j]置为i;否则就update(pre[j],j)，表示的意思是约数j肯定不是第一次出现,将pre[j]以前的区间更新最大约数。如果查询区间的右边界在i处，那么左边界在pre[j]以前就肯定就能取到j。因为num[pre[j]]和num[i]有一个公共约数j，且pre[j]和i被该查询区间所覆盖。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define Maxn 50010

#define lowbit(x) (x&(-x))

using namespace std;

int C[Maxn],n,num[Maxn],pre[Maxn],q,ans[Maxn];

struct QT{

    int l,r,i;

    int operator <(const QT &temp) const

    {

        return r<temp.r;

    }

}qt[Maxn];

int Sum(int pos)//往后找
{

    int sum=;

    while(pos<=n)

    {

        sum=max(sum,C[pos]);

        pos+=lowbit(pos);

    }

    return sum;

}

void update(int pos,int val)//更新pos以前的位置
{

    while(pos)

    {

        C[pos]=max(C[pos],val);

        pos-=lowbit(pos);

    }

}

int main()

{

    int t,i,j;

    scanf("%d",&t);

    while(t--)

    {

        memset(C,,sizeof(C));

        memset(pre,,sizeof(pre));

        scanf("%d",&n);

        for(i=;i<=n;i++)

            scanf("%d",num+i);

        scanf("%d",&q);

        for(i=;i<=q;i++)

        {

            scanf("%d%d",&qt[i].l,&qt[i].r);

            qt[i].i=i;

        }

        sort(qt+,qt++q);

        int r=;

        for(i=;i<=n;i++)

        {

            if(r>q) break;

            for(j=;j*j<=num[i];j++)

            {

                if(num[i]%j) continue;

                if(pre[j]) update(pre[j],j);

                pre[j]=i;

                if(j*j==num[i]) break;

                int k=num[i]/j;

                if(pre[k]) update(pre[k],k);

                pre[k]=i;

            }

            while(qt[r].r==i&&r<=q)

            {

                ans[qt[r].i]=Sum(qt[r].l);

                r++;

            }

        }

        for(i=;i<=q;i++)

            printf("%d\n",ans[i]);

    }

    return ;

}

巴特西

hdu 4630 树状数组

最新文章

热门文章