2.数字对
【题目描述】
小H是个善于思考的学生，现在她又在思考一个有关序列的问题。
她的面前浮现出一个长度为n的序列{ai}，她想找出一段区间[L, R](1 <= L <= R <= n)。
这个特殊区间满足，存在一个k(L <= k <= R)，并且对于任意的i(L <= i <= R)，ai都能被ak整除。这样的一个特殊区间 [L, R]价值为R - L。
小H想知道序列中所有特殊区间的最大价值是多少，而有多少个这样的区间呢？这些区间又分别是哪些呢？你能帮助她吧。
【输入格式】
第一行，一个整数n.
第二行，n个整数，代表ai.
【输出格式】
第一行两个整数，num和val,表示价值最大的特殊区间的个数以及最大价值。
第二行num个整数，按升序输出每个价值最大的特殊区间的L.
【样例输入1】
5
4 6 9 3 6
【样例输出1】
1 3
2
【样例输入2】
5
2 3 5 7 11
【样例输出2】
5 0
1 2 3 4 5
【数据范围】
30%: 1 <= n <= 30 , 1 <= ai <= 32.
60%: 1 <= n <= 3000 , 1 <= ai <= 1024.
80%: 1 <= n <= 300000 , 1 <= ai <= 1048576.
100%: 1 <= n <= 500000 , 1 <= ai < 2 ^ 31.
/*
暴力.
复杂度n*ans左右.
竟然能过.
But But But
我没想到区间判重然后爆零orz.
区间的话只判一维就好.
因为在该ans下左端点只会出现一次.
*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<map>
#define MAXN 500001
#define LL long long
using namespace std;
int s[MAXN],n,m,cut,ans,tot,a[MAXN];
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*f;
}
void slove()
{
for(int i=1;i<=n;i++)
{
int l=1,r=n;
for(int j=i;j>=1;j--)
if(a[j]%a[i]!=0){l=j+1;break;}
for(int j=i;j<=n;j++)
if(a[j]%a[i]!=0){r=j-1 ;break;}
if(r-l==ans) s[++tot]=l;
if(r-l>ans)
{
ans=r-l;
tot=0;
s[++tot]=l;
}
}
tot=unique(s+1,s+tot+1)-s-1;
printf("%d %d
",tot,ans);
for(int i=1;i<=tot;i++)
printf("%d ",s[i]);
}
int main()
{
freopen("pair.in","r",stdin);
freopen("pair.out","w",stdout);
int x,y;
n=read();
for(int i=1;i<=n;i++) a[i]=read();
slove();
return 0;
}/*
考试打到线段树维护就蒙蔽了.
然后树上各种乱判.
其实区间最小值等于区间gcd
就说明这个值在这个区间出现了.
二分一个ans 把区间降到nlogn个.
然后线段树log查询检验.
But 这题卡log 只能得60.
用ST表维护就好了.
*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 500001
#define LL long long
using namespace std;
int s[MAXN],n,m,cut,ans=-1,tot,tmp[MAXN];
struct data{int l,r,lc,rc,ans,min;bool b;}tree[MAXN*4];
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*f;
}
int gcd(int x,int y)
{
if(!y) return x;
else gcd(y,x%y);
}
void Build(int l,int r)
{
int k=++cut;
tree[k].l=l,tree[k].r=r;
if(l==r){
tree[k].b=true;
tree[k].ans=read();
tree[k].min=tree[k].ans;
return ;
}
int mid=(l+r)>>1;
tree[k].lc=cut+1;
Build(l,mid);
tree[k].rc=cut+1;
Build(mid+1,r);
tree[k].ans=gcd(tree[tree[k].lc].ans,tree[tree[k].rc].ans);
tree[k].min=min(tree[tree[k].lc].min,tree[tree[k].rc].min);
}
int querygcd(int k,int l,int r)
{
if(l<=tree[k].l&&tree[k].r<=r) return tree[k].ans;
int tot1=0,tot2=0,mid=(tree[k].l+tree[k].r)>>1;
if(l<=mid) tot1=querygcd(tree[k].lc,l,r);
if(r>mid) tot2=querygcd(tree[k].rc,l,r);
if(tot1&&tot2) return gcd(tot1,tot2);
if(tot1) return tot1;
if(tot2) return tot2;
}
int querymin(int k,int l,int r)
{
if(l<=tree[k].l&&tree[k].r<=r) return tree[k].min;
int tot1=1e9,mid=(tree[k].l+tree[k].r)>>1;
if(l<=mid) tot1=min(tot1,querymin(tree[k].lc,l,r));
if(r>mid) tot1=min(tot1,querymin(tree[k].rc,l,r));
return tot1;
}
bool check(int x)
{
bool flag=false;int total=0;
for(int i=1;i<=n;i++) tmp[i]=0;
for(int i=1;i<=n-x;i++)
{
if(querymin(1,i,i+x)==querygcd(1,i,i+x))
{
tmp[++total]=i;flag=true;
}
}
if(flag&&ans<x)
{
tot=total;
for(int i=1;i<=tot;i++) s[i]=tmp[i];
ans=x;return true;
}
return false;
}
void erfen(int l,int r)
{
int mid;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d %d
",tot,ans);
for(int i=1;i<=tot;i++)
printf("%d ",s[i]);
}
int main()
{
freopen("pair.in","r",stdin);
freopen("pair.out","w",stdout);
int x,y;
n=read();
Build(1,n);
erfen(0,n);
return 0;
}