某次模拟赛的T1。
刚开始怀疑是RMQ......我真是太弱了QAQ
正解是离线操作，把所有询问按r从小到大排序。
然后把数从左到右处理，处理完第i个数，就可以回答所有r==i的询问了。
分解因数，记录下来每个因数上一次出现的位置。
又遇到这个因数，就把上一次的位置加进线段树，把这一次的位置记录下来。
这样线段树里有这个数当且仅当这个数出现了两次以上。
此时这个数显然是备选的合法答案之一，然后询问的时候询问区间最大值就行了。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 int t; 7 int n,m; 8 int a[50005]; 9 int pre[50005]; 10 11 struct query 12 { 13 int ql,qr,ans,id; 14 void get(){scanf("%d%d",&ql,&qr);} 15 }q[50005]; 16 17 int cmp(query w,query e){return w.qr<e.qr;} 18 int cmpb(query w,query e){return w.id<e.id;} 19 20 int mx[200005],lb[200005],rb[200005]; 21 22 void build(int p,int l,int r) 23 { 24 lb[p]=l,rb[p]=r,mx[p]=-1; 25 if(l==r)return; 26 int mid=(l+r)>>1; 27 build(p<<1,l,mid); 28 build(p<<1|1,mid+1,r); 29 } 30 31 void pushup(int p) 32 { 33 mx[p]=max(mx[p<<1],mx[p<<1|1]); 34 } 35 36 void change(int p,int pos,int val) 37 { 38 if(lb[p]==rb[p]) 39 { 40 mx[p]=max(mx[p],val); 41 return; 42 } 43 int mid=(lb[p]+rb[p])>>1; 44 if(pos<=mid)change(p<<1,pos,val); 45 else change(p<<1|1,pos,val); 46 pushup(p); 47 } 48 49 int ask(int p,int l,int r) 50 { 51 if(l<=lb[p]&&r>=rb[p])return mx[p]; 52 int ret=-1,mid=(lb[p]+rb[p])>>1; 53 if(l<=mid)ret=max(ask(p<<1,l,r),ret); 54 if(r>mid)ret=max(ask(p<<1|1,l,r),ret); 55 return ret; 56 } 57 58 void work() 59 { 60 scanf("%d",&n); 61 build(1,1,n); 62 memset(pre,0,sizeof(pre)); 63 for(int i=1;i<=n;i++)scanf("%d",&a[i]); 64 scanf("%d",&m); 65 for(int i=1;i<=m;i++)q[i].get(),q[i].id=i; 66 sort(q+1,q+m+1,cmp); 67 int nw=1; 68 for(int i=1;i<=n;i++) 69 { 70 for(int k=1;k*k<=a[i];k++) 71 { 72 if(a[i]%k)continue; 73 if(pre[k])change(1,pre[k],k); 74 if(pre[a[i]/k]&&a[i]!=k*k) 75 change(1,pre[a[i]/k],a[i]/k); 76 pre[k]=pre[a[i]/k]=i; 77 } 78 while(q[nw].qr==i) 79 { 80 if(q[nw].ql>=q[nw].qr)q[nw].ans=0; 81 else q[nw].ans=ask(1,q[nw].ql,q[nw].qr); 82 nw++; 83 } 84 } 85 sort(q+1,q+m+1,cmpb); 86 for(int i=1;i<=m;i++)printf("%d ",q[i].ans); 87 } 88 89 int main() 90 { 91 scanf("%d",&t); 92 while(t--)work(); 93 return 0; 94 }