正題

題目鏈接:https://www.luogu.com.cn/problem/P3889

---

題目大意

$n$個數的序列，$m$次詢問，每次給出一個區間$[l,r]$，求在區間內和區間外各選一個數使得他們的$gcd$最大

---

解題思路

首先沒有修改且沒有要求強制在線，考慮離線做法。

我們可以將問題轉換為對于求一個與之相交的區間使得該區間兩端點的$gcd$最大。這樣我們可以知道如果對于$k$個點有相同的因子，有$\frac{k(k?1)}{2}$個區間，但是只有相鄰的點構成的區間會對答案造成影響，所以總共只有$k?1$個區間

先考慮如何計算在區間的左邊選擇時的結果。首先我們可以將區間按照右端點從小到大排序，然后用指針掃描右端點，線段樹維護該右端點時的左端點的答案。這樣我們對于每個數可以枚舉他的因子然后在記錄前一個該因子的數的位置即可進行維護

時間復雜度$O(n\sqrt{n}\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+10,L=1e5; int n,m,a[N],pre[N],ans[N]; int w[N*4],lazy[N*4]; struct node{int l,r,num; }q[N]; bool cmp(node x,node y) {return x.r<y.r;} bool cMp(node x,node y) {return x.l>y.l;} void Downdata(int x){w[x<<1]=max(w[x<<1],lazy[x]);lazy[x<<1]=max(lazy[x<<1],lazy[x]);w[x<<1|1]=max(w[x<<1|1],lazy[x]);lazy[x<<1|1]=max(lazy[x<<1|1],lazy[x]);return; } void Change(int x,int L,int R,int l,int r,int val){if(L==l&&R==r){w[x]=max(w[x],val);lazy[x]=max(lazy[x],val);return;}Downdata(x);int mid=(L+R)>>1;if(r<=mid)Change(x<<1,L,mid,l,r,val);else if(l>mid)Change(x<<1|1,mid+1,R,l,r,val);else Change(x<<1,L,mid,l,mid,val),Change(x<<1|1,mid+1,R,mid+1,r,val);w[x]=max(w[x<<1],w[x<<1|1]);return; } int Ask(int x,int L,int R,int pos){if(L==R)return w[x];Downdata(x);int mid=(L+R)>>1;if(pos<=mid)return Ask(x<<1,L,mid,pos);if(pos>mid)return Ask(x<<1|1,mid+1,R,pos);return 0; } int main() {scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);scanf("%d",&m);for(int i=1;i<=m;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].num=i;sort(q+1,q+1+m,cmp);int z=1;for(int i=1;i<=n;i++){for(int k=1;k*k<=a[i];k++)if(a[i]%k==0){if(pre[k])Change(1,1,L,pre[k]+1,i,k);pre[k]=i;if(a[i]/k==k)continue;if(pre[a[i]/k])Change(1,1,L,pre[a[i]/k]+1,i,a[i]/k);pre[a[i]/k]=i;}while(z<=m&&q[z].r<=i){ans[q[z].num]=Ask(1,1,L,q[z].l);z++;}}memset(w,0,sizeof(w));memset(lazy,0,sizeof(lazy));memset(pre,0,sizeof(pre));sort(q+1,q+1+m,cMp);z=1;for(int i=n;i>=1;i--){for(int k=1;k*k<=a[i];k++)if(a[i]%k==0){if(pre[k])Change(1,1,L,i,pre[k]-1,k);pre[k]=i;if(a[i]/k==k)continue;if(pre[a[i]/k])Change(1,1,L,i,pre[a[i]/k]-1,a[i]/k);pre[a[i]/k]=i;}while(z<=m&&q[z].l>=i){ans[q[z].num]=max(ans[q[z].num],Ask(1,1,L,q[z].r));z++;}}for(int i=1;i<=m;i++)printf("%d\n",ans[i]);return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的P3889-[GDOI2014]吃【线段树】的全部內容，希望文章能夠幫你解決所遇到的問題。

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