題意：給一串數字，每次查詢[L,R]中兩個數的gcd的最大值。

解法：容易知道，要使取兩個數讓gcd最大，這兩個數最好是倍數關系，所以處理出每個數的所有倍數，兩兩間根據倍數關系形成一條線段，值為該數。那么每次查詢[L,R]之間兩數gcd的最大值即為查詢[L,R]中值最大的線段，離線所有的查詢數據，然后按右端點坐標從小到大排序，依次往右加入即可。

這里學到了樹狀數組維護最大值的寫法。

代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> using namespace std; #define N 50007int c[N]; struct node {int l,r,v; }a[10*N],Q[N]; int n,pos[N],num[N],ans[N];int cmp(node ka,node kb) { return ka.r < kb.r; } int lowbit(int x) { return x&-x; }void modify(int x,int val) {while(x > 0){c[x] = max(c[x],val);x -= lowbit(x);} }int getmax(int x) {int res = 0;while(x <= n){res = max(res,c[x]);x += lowbit(x);}return res; }int main() {int t,i,j,x,q,tot;scanf("%d",&t);while(t--){scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&x);pos[x] = i;c[i] = 1;}tot = 0;for(i=2;i<=n/2;i++){int k = 0;for(j=i;j<=n;j+=i) //i的倍數num[k++] = pos[j];sort(num,num+k);for(j=1;j<k;j++){a[tot].l = num[j-1];a[tot].r = num[j];a[tot++].v = i;}}scanf("%d",&q);for(i=0;i<q;i++){scanf("%d%d",&Q[i].l,&Q[i].r);Q[i].v = i;}sort(a,a+tot,cmp);sort(Q,Q+q,cmp);j = 0;for(i=0;i<q;i++){if(Q[i].l == Q[i].r){ans[Q[i].v] = 0;continue;}while(j < tot && a[j].r <= Q[i].r)modify(a[j].l,a[j].v),j++;ans[Q[i].v] = getmax(Q[i].l);}for(i=0;i<q;i++)printf("%d\n",ans[i]);}return 0; } View Code

?

轉載于:https://www.cnblogs.com/whatbeg/p/3989065.html

總結

以上是生活随笔為你收集整理的HDU 4630 No Pain No Game 树状数组+离线操作的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。