给你一个序列s，求出所有最长的区间[l,r]使得存在一个k∈[l,r]且对于任何i∈[l,r]都有s[k]|s[i]
显然如果这个k存在，那么s[k]一定是s[l]~s[r]的最小值
现在问题就成了，求一个最长的区间使得s[l]~s[r]的最小值=s[l]~s[r]的gcd
那么我们可以二分答案，而求一个区间最小和gcd都可以用ST表完成，所以整体复杂度nlg^2n
（虽然说这是solution的方法但是不是最快的方法，最快的方法是枚举k，让后向两边暴力扫描法，复杂度是n^2的但是跑起来非常快！）
正解：313ms
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
inline int Min(int a,int b){ return a<b?a:b; }
inline int gcd(int a,int b){
for(int c;b;a=b,b=c) c=a%b;
return a;
}
int preLog[500010],n,w[500010];
vector<int> A;
struct ST_list{
int (*f)(int,int) ;
int g[20][500010];
void init(int* s,int (*f1)(int,int) ){
f=f1;
memcpy(g[0]+1,s+1,n<<2);
for(int i=n;i;--i)
for(int j=1;i+(1<<j)-1<=n;++j)
g[j][i]=f(g[j-1][i],g[j-1][i+(1<<j-1)]);
}
int query(int l,int r){
int k=preLog[r-l+1];
return f(g[k][l],g[k][r-(1<<k)+1]);
}
} s1,s2;
bool ok(int len){
int M=n-len;
for(int i=1;i<=M;++i)
if(s1.query(i,i+len)==s2.query(i,i+len)) return 1;
return 0;
}
int main(){
preLog[1]=0;
for(int i=2,j=0;i<=500010;++i){
if(i==(1<<j+1)) ++j;
preLog[i]=j;
}
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",w+i);
s1.init(w,Min); s2.init(w,gcd);
int l=0,r=n-1;
for(int m;l<r;){
m=l+r+1>>1;
if(ok(m)) l=m;
else r=m-1;
}
n-=l;
for(int i=1;i<=n;++i)
if(s1.query(i,i+l)==s2.query(i,i+l)) A.push_back(i);
printf("%d %d
",A.size(),l);
for(int i=0,z=A.size();i<z;++i) printf("%d ",A[i]);
}
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 500010
using namespace std;
int a[N],ans[N];
int main()
{
int n,num=0,val=0;
cin>>n;
fo(i,1,n)
{
scanf("%d",&a[i]);
if(a[i]==1)
{
cout<<1<<' '<<n-1<<endl<<1;
return 0;
}
}
fo(k,1,n)
{
if(a[k]==0) continue;
int l=k,r=k;
while(a[l-1]%a[k]==0 && l>1) l--;
while(a[r+1]%a[k]==0 && r<n) r++;
if(r-l==val && l!=ans[num]) ans[++num]=l;
if(r-l>val)
{
fo(i,1,num) ans[i]=0;
val=r-l,ans[num=1]=l;
}
}
cout<<num<<' '<<val<<endl;
fo(i,1,num) printf("%d ",ans[i]);
}