本文主要是介绍hdu 5869 Different GCD Subarray Query 预处理 + 离线，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
// hdu 5869 Different GCD Subarray Query 预处理 + 离线
//
// 题目链接：
//
// http://acm.split.hdu.edu.cn/showproblem.php?pid=5869
//
// 题目大意：
//
// 给定数组，求[L,R]段中所有子段的不同gcd的种类
//
// 解题思路：
//
// 根据XJ的题解，固定左端点的不同GCD的值，这个值是不超过logA
// 这样，我们可以预处理出对于当前a{i}，求出[1,i-1]的gcd值，然后
// 将查询按照右端点排个序，固定右端点，用树状数组求出[L，i]的gcd
// 的个数。当然，我们必须每次加入gcd到最右边界，因为只有最右边界
// 是最小的区间，在最右边界之前的区间都可以去到这个gcd的值。所以
// 用个vis数组存储边界
//
// 感悟：
//
// 这类题以前没有接触过，所以，当看到XJ的题解的时候，整个人处
// 于懵X状态，研究了差不多一个小时吧（ok，说实话是取得min），看着
// 代码还是挺亲切的，预处理还挺好理解的，之后的按右边界，可以放入
// vector中，省去排序的时间，只是因为各种手残，GG一下午。继续努力
// ^_^#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <stack>
#include <set>
#include <queue>
#include <algorithm>using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 1e5 + 8;int a[MAXN];
int ans[MAXN];
vector<pii> gc[MAXN];
vector<pii> query[MAXN];int vis[MAXN * 10];
int n,q;struct SegmentTree{#define lowbit(x) (x & (-x))int sum[MAXN];void init(){memset(sum,0,sizeof(sum));}void update(int x,int v){while(x <= n){sum[x] += v;x += lowbit(x);}}int getSum(int x){int ans = 0;while(x){ans += sum[x];x -= lowbit(x);}return ans;}
}it;void init(){for (int i = 0;i <= n;i ++){gc[i].clear();query[i].clear();}memset(vis,0,sizeof(vis));it.init();
}void input(){for (int i = 1;i <= n;i ++)scanf("%d",a + i);for (int i = 1;i <= n;i ++){int x = a[i];int y = i;for (int j = 0; j < gc[i - 1].size();j ++){int res = __gcd(gc[i - 1][j].first,x);if (x != res){gc[i].push_back(make_pair(x,y));x = res;y = gc[i - 1][j].second;}}gc[i].push_back(make_pair(x,y));}for (int i = 1;i <= q;i ++){int l,r;scanf("%d%d",&l,&r);query[r].push_back(make_pair(l,i));}for (int i = 1;i <= n;i ++){for (int j = 0;j < gc[i].size();j ++){int res = gc[i][j].first;int ind = gc[i][j].second;if (vis[res])it.update(vis[res],-1);vis[res] = ind;it.update(ind,1);}for (int j = 0;j < query[i].size();j ++){int l = query[i][j].first;int ind = query[i][j].second;ans[ind] = it.getSum(i) - it.getSum(l - 1);}}for (int i = 1;i <= q;i++){printf("%d\n",ans[i]);}
}int main(){while(scanf("%d%d",&n,&q)!=EOF){init();input();}return 0;
}
这篇关于hdu 5869 Different GCD Subarray Query 预处理 + 离线的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
