首页 > 代码库 > HDU 5869 Different GCD Subarray Query 离线+树状数组
HDU 5869 Different GCD Subarray Query 离线+树状数组
Different GCD Subarray Query
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].
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≤N,Q≤100000
1≤ai≤1000000
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≤N,Q≤100000
1≤ai≤1000000
Output
For each query, output the answer in one line.
Sample Input
5 31 3 4 6 93 52 51 5
Sample Output
666
题意:
长度n的序列, m个询问区间[L, R], 问区间内的所有子段的不同GCD值有多少种.
题解:
固定右端点
预处理出 每个点向左延伸 的 不同gcd值
这样的 值不会超过log a 个
然后问题就变成了 问你一段区间内不同 gcd 值有多少,值是很少的 (询问一个区间有多少颜色的题型)
树状数组维护就可以了
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#include<vector>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair<int,int>#define MP make_pairtypedef long long LL;const long long INF = 1e18;const double Pi = acos(-1.0);const int N = 1e6+10, M = 1e2+11, mod = 1e9+7, inf = 2e9;int n,q,a[N],ans[N];int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b);}vector<pii> G[N];struct QQ{ int l,r,id; bool operator < (const QQ &a) const { return a.r > r; }}Q[N];int C[N],vis[N];void update(int x,int c) { for(int i =x; i < N; i+=i&(-i)) C[i] += c;}int ask(int x) { int s =0 ; for(int i = x; i; i-= i & (-i))s += C[i]; return s;}int main() { while(scanf("%d%d",&n,&q)!=EOF) { for(int i = 1; i <= n; ++i) scanf("%d",&a[i]); for(int i = 0; i <= n; ++i) G[i].clear(); for(int i = 1; i <= n; ++i) { int x = a[i]; int y = i; for(int j = 0; j < G[i-1].size(); ++j) { int res = gcd(x,G[i-1][j].first); if(x != res) { G[i].push_back(MP(x,y)); x = res; y = G[i-1][j].second; } } G[i].push_back(MP(x,y)); } memset(C,0,sizeof(C)); memset(vis,0,sizeof(vis)); for(int i = 1; i <= q; ++i) {scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].id = i;} sort(Q+1,Q+q+1); for(int R = 0, i = 1; i <= q; ++i) { while(R < Q[i].r) { R++; for(int j = 0; j < G[R].size(); ++j) { int res = G[R][j].first; int ids = G[R][j].second; if(vis[res]) update(vis[res],-1); vis[res] = ids; update(vis[res],1); } } ans[Q[i].id] = ask(R) - ask(Q[i].l-1); } for(int i = 1; i <= q; ++i) cout<<ans[i]<<endl; } return 0;}
HDU 5869 Different GCD Subarray Query 离线+树状数组
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。