HDU5869 树状数组

90 阅读 0 评论 60 点赞

我是靠谱客的博主落后小笼包，这篇文章主要介绍HDU5869 树状数组，现在分享给大家，希望可以做个参考。

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
2
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

树状数组的题…
思路就是先取所有的gcd一个一个找，大小区间都算
重复的就去重
还得多理解。。

补充：昨天有一些没想明白的地方但是太晚了就没在意…..
之所以不能全部处理完了再输出的原因就是因为
那个qujian 数组在遍历完了更高的区间以后存的下标就会变化
最后gs出来的不是想要的那个值

复制代码

#include<stdio.h>
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<memory.h>
#include<vector>
using namespace std;
int q, w;
int di[100020];
int ci[100020];
int qujian[1000200];
int lowb(int x) { return x&(-x); }
int gcd(int a, int b)
{
    if (b == 0) return a;
    return gcd(b, a%b);
}
int gs(int x)//这是得到的值
{
    int s = 0;
    for (int a = x;a > 0;a -= lowb(a))s += ci[a];
    return s;
}
struct p
{
    int zuo, xiabiao;
};
vector<p>xia[100005];
int yuyu[100005];
void gengxin(int dizhi, int zhi){for (int a = dizhi;a <= q;a += lowb(a))ci[a] += zhi;}
int main()
{
    while (cin >> q >> w)
    {
        memset(di, 0, sizeof(di));
        memset(ci, 0, sizeof(ci));
        memset(qujian, 0, sizeof(qujian));
        for (int a = 1;a <= q;a++)scanf("%d", &di[a]),xia[a].clear();
        int qq, ww;
        for (int a = 1;a <= w;a++)
        {
            scanf("%d%d", &qq, &ww);
            xia[ww].push_back({qq,a});
        }
        for (int a = 1;a <= q;a++)
        {
            for (int b = a, x = di[b];b > 0;b--, x = gcd(x, di[b]))
            {
                if (b > qujian[x])
                {
                    if (qujian[x] != 0)gengxin(qujian[x], -1);//这是个判断重复的好办法
                    gengxin(b, 1);//每当碰见了就更新一次
                    qujian[x] = b;
                }
                if (x == 1)break;
            }
            for (int b = 0;b < xia[a].size();b++)yuyu[xia[a][b].xiabiao] = -gs(xia[a][b].zuo-1) + gs(a );
        }
        for (int a = 1;a <= w;a++)printf("%dn", yuyu[a]);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<stdio.h>
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<memory.h>
#include<vector>
using namespace std;
int q, w;
int di[100020];
int ci[100020];
int qujian[1000200];
int lowb(int x) { return x&(-x); }
int gcd(int a, int b)
{
    if (b == 0) return a;
    return gcd(b, a%b);
}
int gs(int x)//这是得到的值
{
    int s = 0;
    for (int a = x;a > 0;a -= lowb(a))s += ci[a];
    return s;
}
struct p
{
    int zuo, xiabiao;
};
vector<p>xia[100005];
int yuyu[100005];
void gengxin(int dizhi, int zhi){for (int a = dizhi;a <= q;a += lowb(a))ci[a] += zhi;}
int main()
{
    while (cin >> q >> w)
    {
        memset(di, 0, sizeof(di));
        memset(ci, 0, sizeof(ci));
        memset(qujian, 0, sizeof(qujian));
        for (int a = 1;a <= q;a++)scanf("%d", &di[a]),xia[a].clear();
        int qq, ww;
        for (int a = 1;a <= w;a++)
        {
            scanf("%d%d", &qq, &ww);
            xia[ww].push_back({qq,a});
        }
        for (int a = 1;a <= q;a++)
        {
            for (int b = a, x = di[b];b > 0;b--, x = gcd(x, di[b]))
            {
                if (b > qujian[x])
                {
                    if (qujian[x] != 0)gengxin(qujian[x], -1);//这是个判断重复的好办法
                    gengxin(b, 1);//每当碰见了就更新一次
                    qujian[x] = b;
                }
                if (x == 1)break;
            }
            for (int b = 0;b < xia[a].size();b++)yuyu[xia[a][b].xiabiao] = -gs(xia[a][b].zuo-1) + gs(a );
        }
        for (int a = 1;a <= w;a++)printf("%dn", yuyu[a]);
    }
    return 0;
}