首页 > 代码库 > HDU 5869 Different GCD Subarray Query 树状数组 + 一些数学背景

HDU 5869 Different GCD Subarray Query 树状数组 + 一些数学背景

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

题意:给定一个数组,然后给出若干个询问,询问[L, R]中,有多少个子数组的gcd是不同的。

就是[L, R]中不同区间的gcd值,有多少个是不同的。

 

 给个样例

3 3
7 7 7
1 2
1 3
3 3

 

数学背景:

一个数字和若N个数字不断GCD,其结果只有loga[i]种,为什么呢?因为可以把a[i]质因数分解,其数目最多是loga[i]个数字相乘。(最小的数字是2,那么loga[i]个2相乘也爆了a[i]了)

所以,考虑以a[i]为结尾的序列,有多少个不同的gcd,可以记录下。

比如样例。括号里的依次是gcd值和a[i]这个数字最早与那个位置gcd,其值是val、

1、    3、    4、    6、    9

(1, 1)    (3, 2)   (4, 3)   (6, 4)   (9, 5)

      (1, 1)   (1, 2)   (2, 3)   (3, 4)

                 (1, 2)   (1, 3)    //9这个数字在[3, 5]中一路gcd,就能得到1

这里其实已经维护了左端点了,要求左端点尽量大。

1、为什么要维护左端点,因为答案给出的是[L, R]这段区间的不同gcd,如果你预处理的时候,R和L - 1得到的gcd是不能算进去的。

2、要求左端点尽量大,那是因为我后来要对R排序,尽量往R靠,结果是最优的,(可以参考下求区间不同数字个数的方法。后面再写。)

 

然后就是套路了。把得到的gcd往左端点里塞。?,这是重点,一开始的时候我把不同的gcd往右端点塞了,这是不对的,因为往又端点塞的话,R与L - 1的gcd就会被你算进去了,所以会wa。

book[x]表示x这个值出现的最右的那个位置。

技术分享
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;

#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 1000000 + 20;
const int N = 1000000 + 20;
int c[maxn];
int lowbit(int x) {
    return x & (-x);
}
void upDate(int pos, int val) {
    while (pos <= N - 20) {
        c[pos] += val;
        pos += lowbit(pos);
    }
}
int query(int pos) {
    int ans = 0;
    while (pos) {
        ans += c[pos];
        pos -= lowbit(pos);
    }
    return ans;
}
int n, q;
int a[maxn];
struct node {
    int L, R;
    int id;
    bool operator < (const struct node & rhs) const {
        return R < rhs.R;
    }
}b[maxn];
int book[maxn];
int ans[maxn];
void work() {
    memset(book, 0, sizeof book);
    memset(c, 0, sizeof c);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= q; ++i) {
        scanf("%d%d", &b[i].L, &b[i].R);
        if (b[i].L > b[i].R) swap(b[i].L, b[i].R);
        b[i].id = i;
    }
    sort(b + 1, b + 1 + q);
    int cur = 1;
//    for (int i = 1; i <= q; ++i) {
//        cout << b[i].L << " " << b[i].R << endl;
//    }
    for (int i = 1;  i <= q; ++i) {
        for (int j = cur; j <= b[i].R; ++j) {
            int x = a[cur];
            for (int k = cur; k >= 1; k--) {
                if (book[x] < k) { //左端点只能尽量右靠,左边的不管,样例:7 7 7
                    if (book[x]) { //树状数组不能从0开始
                        upDate(book[x], -1);
                    }
                    book[x] = k; //不同的gcd,压到左端点
                    upDate(book[x], 1);
                }
//                if (book[x] > k) while(1);
//                book[x] = k;
//                upDate(book[x], 1);
                if (k == 1) break;
                if (x == 1) break;
                x = __gcd(x, a[k - 1]);
            }
            cur++;
        }
        ans[b[i].id] = query(b[i].R) - query(b[i].L - 1);
    }
    for (int i = 1;  i <= q; ++i) {
        printf("%d\n", ans[i]);
    }

}
int main() {
#ifdef local
    freopen("data.txt","r",stdin);
#endif
    while (scanf("%d%d", &n, &q) != EOF) work();
    return 0;
}
View Code

 

关于树状数组

3.1、求逆序对:首先先把数据离散化,因为树状数组覆盖的区间是1—max这样的,不离散的话开不到那么大的数组。例如离散后是:5、2、1、4、3、思路是:插入5,add(5,1),把pos为5的地方设置为1,然后ans += i - get_sum(5);  i的意思是当前插入了i个数,然后get_sum()是当前有多少个数比5少,其实就是问1—5之间存在多少个数,那当然是比5小的啦。一减,就是关于5逆序对个数。eg:关于2的逆序对个数是1对。

LL get_inversion (int a[],int lena)  //求逆序对个数

{

    LL ans = 0;//逆序对一般都很多,需要用LL

    for (int i=1;i<=lena;++i)    // a[]={5,2,1,4,3} ans=6;

    {                   // a[]={5,5,5,5,5} ans=0; 逆序对严格大于

        add(a[i],1);  ans += i-get_sum(a[i]);

    }

    return ans;

}

关于数据离散化,可以开一个结构体,保存val和pos,然后根据val排序一下,根据pos从小到大赋值即可。for (int i=1;i<=n;++i) a[book[i].pos]=i; //从小到大离散。a[3]=1,a[1]=2等等

{9,1,0,5,4}  离散化后  {5,2,1,4,3}

 

3.2、求解区间不同元素个数,离线算法。复杂度O(q + nlog(n))

设树状数组的意义是:1--pos这个段区间的不同元素的种类数。怎么做?就是add(pos,1);在这个位置中+1,就是说这个位置上元素种类+1。然后先把询问按R递增的顺序排序。因为这里是最优的,我每次尽量往R靠,使得查询不重不漏。什么意思呢?就是假如有:2、1、3、5、1、7的话。一开始的[1,4]这段数字全部压进树状数组,用个数组book[val],表示val这个元素出现的最右的位置,因为我们需要删除重复的,也是要尽量往右靠。到达pos=5这个位置的时候,注意了,因为1是出现过的book[1] = 2,所以我们要做的是把2这个位置出现元素的种类数-1,就是add(book[1],  -1)。然后把第五个位置出现的元素种类数+1,就是add(5,1)。为什么呢?因为你尽量把种类往右靠,因为我们的R是递增的,这样,你使得查询[4,6]成为可能,因为我那个1加入来了,而不是一直用pos=2那个位置的1,再者,查询[4,7]的话,一样的意思,因为中间的1进来了。所以我们因为尽量往右靠,毕竟我们都把query按R排序了。还有这个只能离线,一直预处理ans[i]表示第i个询问的ans。更新到[4,7]后,查询[1,2]已经不可能了,因为很明显,pos=2这个位置已经被删除了。

void work ()

{

    scanf("%d",&n);

    for (int i=1;i<=n;++i) scanf("%d",&a[i]);

    int q; scanf("%d",&q);

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

    {

        scanf("%d%d",&query[i].L,&query[i].R);

        query[i].id = i; //记录ans

    }

    sort(query+1,query+1+q);

    int cur = 1;

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

    {

        for (int j=cur;j<=query[i].R;++j)

        {

            if (book[a[j]])

                add(book[a[j]],-1); //del 这个位置

            book[a[j]]=j; //更新这个位置的最右值

            add(j,1); //这个位置出现了新元素

        }

        cur = query[i].R+1; //表示现在预处理到这个位置了。不能往回查,而且也不会往回

        ans[query[i].id] = get_sum(query[i].R) - get_sum(query[i].L-1); //区间减法

    }

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

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

}

HDU 5869 Different GCD Subarray Query 树状数组 + 一些数学背景