HDU - 5869 Different GCD Subarray Query 树状数组离线处理

134 阅读 0 评论 89 点赞

我是靠谱客的博主无奈小刺猬，这篇文章主要介绍HDU - 5869 Different GCD Subarray Query 树状数组离线处理，现在分享给大家，希望可以做个参考。

传送门：HDU5869

题意：给出一个长度为n的序列和m次询问，每次询问给出l，r，求[l, r]区间内所有子序列不同gcd的个数。

思路：首先明确对于一个序列a[l...r]的所有以a[l]开头的子序列，所能得到的不同gcd的个数最多有log(a[l])个。那么这个题中我们就可以对于每一个位置，预处理出以该位置为结尾的所有不同gcd的最大左边界（即L至少要到这个位置才能在L~R这个区间中能形成这个gcd），然后将所有询问按右端点排序，每次处理询问的时候将所有小于r的位置预处理出来的值用树状数组维护一下就好了。

代码：

复制代码

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
typedef pair<int,int> P;
const int MAXN = 1000100;
struct node{
	int l, r, id;
	bool operator < (node a) const
	{
		return r < a.r;
	}
}Q[MAXN];
int bit[MAXN], a[MAXN];
void add(int i, int x)
{
	while(i < MAXN)
	{
		bit[i] += x;
		i += i & -i;
	}
}
int sum(int i)
{
	int res = 0;
	while(i)
	{
		res += bit[i];
		i -= i & -i;
	}
	return res;
}
vector<P> gcd[MAXN];
int book[MAXN], ans[MAXN];
int main()
{
	int n, q, tmp, id;
	while(cin >> n >> q)
	{
		memset(book, 0, sizeof(book));
		memset(bit, 0, sizeof(bit));
		for(int i = 1; i <= n; i++)
		scanf("%d", a + i), gcd[i].clear();
		for(int i = 1; i <= n; i++)
		{
			gcd[i].push_back(P(a[i], i));
			for(int j = 0; j < gcd[i - 1].size(); j++)
			{
				tmp = __gcd(a[i], gcd[i - 1][j].first);
				if(tmp != gcd[i][gcd[i].size() - 1].first)
				gcd[i].push_back(P(tmp, gcd[i - 1][j].second));
			}
		}
		for(int i = 0; i < q; i++)
		scanf("%d %d", &Q[i].l, &Q[i].r), Q[i].id = i;
		sort(Q, Q + q);
		int last = 1;
		for(int i = 0; i < q; i++)
		{
			while(last <= Q[i].r)
			{
				for(int j = 0; j < gcd[last].size(); j++)
				{
					tmp = gcd[last][j].first;
					id = gcd[last][j].second;
					if(book[tmp])
					{
						if(book[tmp] < id)
						{
							add(book[tmp], -1);
							add(id, 1);
							book[tmp] = id;
						}
					}
					else
					{
						add(id, 1);
						book[tmp] = id;
					}
				}
				last++;
			}
			ans[Q[i].id] = sum(Q[i].r) - sum(Q[i].l - 1);
		}
		for(int i = 0; i < q; i++)
		printf("%dn", ans[i]);
	}
 	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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
typedef pair<int,int> P;
const int MAXN = 1000100;
struct node{
	int l, r, id;
	bool operator < (node a) const
	{
		return r < a.r;
	}
}Q[MAXN];
int bit[MAXN], a[MAXN];
void add(int i, int x)
{
	while(i < MAXN)
	{
		bit[i] += x;
		i += i & -i;
	}
}
int sum(int i)
{
	int res = 0;
	while(i)
	{
		res += bit[i];
		i -= i & -i;
	}
	return res;
}
vector<P> gcd[MAXN];
int book[MAXN], ans[MAXN];
int main()
{
	int n, q, tmp, id;
	while(cin >> n >> q)
	{
		memset(book, 0, sizeof(book));
		memset(bit, 0, sizeof(bit));
		for(int i = 1; i <= n; i++)
		scanf("%d", a + i), gcd[i].clear();
		for(int i = 1; i <= n; i++)
		{
			gcd[i].push_back(P(a[i], i));
			for(int j = 0; j < gcd[i - 1].size(); j++)
			{
				tmp = __gcd(a[i], gcd[i - 1][j].first);
				if(tmp != gcd[i][gcd[i].size() - 1].first)
				gcd[i].push_back(P(tmp, gcd[i - 1][j].second));
			}
		}
		for(int i = 0; i < q; i++)
		scanf("%d %d", &Q[i].l, &Q[i].r), Q[i].id = i;
		sort(Q, Q + q);
		int last = 1;
		for(int i = 0; i < q; i++)
		{
			while(last <= Q[i].r)
			{
				for(int j = 0; j < gcd[last].size(); j++)
				{
					tmp = gcd[last][j].first;
					id = gcd[last][j].second;
					if(book[tmp])
					{
						if(book[tmp] < id)
						{
							add(book[tmp], -1);
							add(id, 1);
							book[tmp] = id;
						}
					}
					else
					{
						add(id, 1);
						book[tmp] = id;
					}
				}
				last++;
			}
			ans[Q[i].id] = sum(Q[i].r) - sum(Q[i].l - 1);
		}
		for(int i = 0; i < q; i++)
		printf("%dn", ans[i]);
	}
 	return 0;
}