本文主要是介绍hdu 4630 树状数组+离线操作+GCD，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=4630
重新认识了树状数组。
首先要记住那个树形的图，然后+或-lowbit(i)是自己根据具体问题设定的，不要死于+或者-，
树状数组的特点：
1、+lowbit(i)可以到达包含结点i的上一层父节点 所以用于值的更改
2、-lowbit(i)可以到达不包含i所代表区间的上一层父节点 所以用于值的求和---每个不相交的段加起来
3、C[i]的含义也是根据具体问题去做设定的，但是c[i]覆盖了a[i-2^lowbit(i)+1]...a[i]这个长为lowbit(i)的区间
然后谈本题：
pre[i]见注释
当读到num[i]的时候，对num[i]的每个因子v，[1...pre[v]]都更新max(v,c[j]) ，因为此时离线处理的时候，会处理区间[l,r]的r==i的区间，把[1...pre[v]]都更新max(v,c[j]) ，就保证了查询l<=pre[v]的时候，包含了max(v,c[j]) ，而l>pre[v]的查询，不包含v的影响
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;#define ls(rt) rt*2
#define rs(rt) rt*2+1
#define ll long long
#define ull unsigned long long
#define rep(i,s,e) for(int i=s;i<e;i++)
#define repe(i,s,e) for(int i=s;i<=e;i++)
#define CL(a,b) memset(a,b,sizeof(a))
#define IN(s) freopen(s,"r",stdin)
#define OUT(s) freopen(s,"w",stdout)const int MAXN = 50000+100;
struct Query{int l,r;int id;bool operator < (const Query &t)const{return r<t.r;}
}q[MAXN];
int N,c[MAXN*2],pre[MAXN],num[MAXN],ans[MAXN];//
inline int lowbit(int x){return x&(-x);}
void update(int i, int v)
{while(i>0){c[i]=max(c[i],v);i-=lowbit(i);}
}
int query(int x)
{int ret=0;while(x<=N){ret=max(c[x],ret);x+=lowbit(x);}return ret;
}vector<int>divs[MAXN];
void caldivs()
{for(int i=1;i<MAXN;i++)for(int j=i;j<MAXN;j+=i)divs[j].push_back(i);
}void init()
{CL(c,0);CL(pre,0);
}int main()
{//IN("hdu4630.txt");int ncase;caldivs();scanf("%d",&ncase);while(ncase--){init();scanf("%d",&N);for(int i=1;i<=N;i++)scanf("%d",&num[i]);int Q;scanf("%d",&Q);for(int i=1;i<=Q;i++){scanf("%d%d",&q[i].l,&q[i].r);q[i].id=i;}sort(q+1,q+1+Q);for(int i=1,k=1;i<=N;i++){int x=num[i];for(int j=0;j<divs[x].size();j++){int y=divs[x][j];if(pre[y])//说明现在y是第二次出现 前一次出现位置是pre[y]，此次是iupdate(pre[y],y);//维护c[i]为pre[y]到i的gcdpre[y]=i;}while(q[k].r==i && k<=Q){ans[q[k].id]=query(q[k].l);k++;}}for(int i=1;i<=Q;i++){printf("%d\n",ans[i]);}}return 0;
}
这篇关于hdu 4630 树状数组+离线操作+GCD的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
