D. 铁路
小S有一个长度为(n)的序列。
一个区间([L,R])是好的，当且仅当存在(kin [L,R])
使得对于任意的(iin [L,R]),(a_k | a_i)。
现在，小S想要知道，最长的好的区间是多少，并且这些区间是什么。
输入格式
第一行一个整数(n)。
接下来一行(n)个数，第(i)个表示(a_i)。
输出格式
第一行两个数，(m)和(len)分别表示最长的好区间个数以及这些区间的(R-L)。
接下来一行(m)个数，按升序输出每个最长的好区间的左端点。
样例
样例一
input
5
4 6 9 3 6
output
1 3
2
样例二
input
5
2 3 5 7 11
output
5 0
1 2 3 4 5
约定与限制
对于(30\%) 的数据，满足 $ n le 30,1le a_ile 32$。
对于(60\%) 的数据，满足 (n le 3000,1le a_ile 1024)。
对于(80\%) 的数据，满足 (nle 300000,1le a_ile 1048576)。
对于(100\%) 的数据 ，满足 (1 le n le 5 imes 10^5,1le a_i< 2^{31}) 。
时间限制:1s
空间限制:512MB
解题报告
题意理解
寻找一段区间，要求这段区间满足：
- 至少存在一个位置(k)，(a_k)可以整除这个区间所有的数(a_i) 。
- 区间长度尽量长
这样的区间有很多个，因此题目要求
- 输出有多少个合法区间
- 这些合法区间的左端点。
(60pts)解析
拿到这道题目，我们发现，(60pts)的(n)取值范围很小，可以忍受(O(n^2))的时间复杂度。
因此我们来对本题，进行初步分析。
首先我们发现，这个(k)一定在这个区间内，而且区间内，所有的数都是他的倍数。
那么，如果说，此时我确定了(k)这个坐标，那么，这个最长区间其实是可以确定下来了。
我们不妨设：
那么根据题意
我们可以得出思路。
- 首先命令(l=k)
- 如果(a_{l-1})是(k)的倍数，那么(l=l-1)，否则此时(l)为最小左区间
- 同理，命令(r=k)
- 如果(a_{r+1})是(k)的倍数，那么(r=r+1)，否则此时(r)为最大右区间
代码如下
//60~100pts & C++11
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+20;
int a[N],s[N],n,m;
vector<int> g[N];
inline void init()
{
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
int ans=0;
for(int i=1; i<=n; i++)
{
int l=i,r=i,ans1=0;//忽略位置k，所以ans1=0
while((l-1) && a[l-1]%a[i]==0)//左区间拓展
l--,ans1++;
while((r+1)<=n && a[r+1]%a[i]==0)//右区间拓展
r++,ans1++;
if (g[ans1].empty() || l>g[ans1].back())
g[ans1].push_back(l);//长度为ans1的区间，记录左区间点
ans=max(ans,ans1);//算出最长好区间
}
printf("%d %d
",g[ans].size(),ans);
for(int s:g[ans])
printf("%d ",s);
}
signed main()
{
// freopen("ff.in","r",stdin);
init();
return 0;
}
期望得分(60pts)，实际得分(100pts)
实际运行时间，是标程(frac{1}{10})
原因：数据太水了
(100pts)解析
我们发现，在这里的话，其实具有单调性质
如果说有一个区间([l,r])满足条件。
假如说(a ge l,b le r，a le k le b)
那么([a,b])一定满足条件.
因此长区间满足条件，那么包含(k)的短区间，肯定也满足条件。
这样的话，我们为什么不二分(R-L)，这个答案呢？
因为
既然如此，那么现在的当务之急就是，如何判断存在这样的一个区间呢？
如果说
这里的意思是，一个区间的最大公约数(=)一个区间的最小数
那么这个区间肯定是合法的，反之必然。
两者互为充要条件。
这是为什么？
充分性证明
命题：区间合法是性质满足的充分条件
因为，我们发现，(a_k)一定是这个区间中的最小数。
否则，如果存在一个数，比他小，那么无法满足整除性质。
所以区间最小数必然是(a_k)
同样的，为什么最大公约数也必须是(a_k)呢？
因为，如果(a_k)是最小数，而最大公约数不可能大于最小数，只能小于等于它。
其次，又因为此时区间是合法的，所有数都是他的倍数，所以最大公约数是它。
所以充要性成立
必要性证明
命题：区间合法是性质满足的必要条件
因为:
区间所有数他们的最大公约数是(s)
然后，此时区间中存在一个最小数的值等于(s)
那么也就是说，在区间中，存在一个数，其他数都是它的倍数。
那么这不就是合法区间的定义吗？
所以必要性成立！
现在我们考虑，如何实现，快速求区间最大公约数和区间最小值。
我们观察到，这里面所有数都是固定不变的，也就是数据静态
所以，我们可以使用由倍增处理的(ST)表，来完成本题。
当然你也可以使用线段树暴力完成。
代码解析
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+20;
int f_gcd[N][21],f_min[N][21],n,a[N];
vector<int> g[N];//g[x]存储R-L=x的区间左端点
int gcd(int a,int b)
{
return !b?a:gcd(b,a%b);
}
inline void pre()//倍增预处理
{
for(int i=1; i<=n; i++)//0，在这里表示[i,i],而不是[i,i+1]
f_gcd[i][0]=f_min[i][0]=a[i];
for(int j=1; j<=20; j++)
for(int i=1; i<=n; i++)
if (i+(1<<j)-1<=n)
{
f_gcd[i][j]=gcd(f_gcd[i][j-1],f_gcd[i+(1<<j-1)][j-1]);
f_min[i][j]=min(f_min[i][j-1],f_min[i+(1<<j-1)][j-1]);
}
}
inline void init()
{
// freopen("ff.in","r",stdin);
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
}
inline int Query_Min(int l,int r)//查询区间[l,r]的最小值,ST表做法
{
int k=log2(r-l+1);
return min(f_min[l][k],f_min[r-(1<<k)+1][k]);
}
inline int Query_Gcd(int l,int r)//查询区间[l,r]的最大公约数，ST表做法
{
int k=log2(r-l+1);
return gcd(f_gcd[l][k],f_gcd[r-(1<<k)+1][k]);
}
inline int check(int x)
{
for(int l=1; l+x<=n; l++)//枚举左端点
{
int r=l+x;//枚举右端点
if (Query_Min(l,r)==Query_Gcd(l,r))//此时最小值=最大公约数,说明存在这个k
g[x].push_back(l);
}
return !g[x].empty();//是否有合法区间
}
inline void work()
{
int l=-1,r=n-1;//开-1，是为了保证mid=0可以取到
while(l<r)//这里二分R-L,也就是区间长度-1
{
int mid=l+r+1>>1;
if (check(mid))//判断是否存在该区间长度
l=mid;
else
r=mid-1;
}
printf("%d %d
",g[r].size(),r);
for(int s:g[r])
printf("%d ",s);
}
signed main()
{
init();
pre();
work();
return 0;
}