D. 铁路
小S有一个长度为$n$的序列。
一个区间$[L,R]$是好的，当且仅当存在$k\in [L,R]$
使得对于任意的$i\in [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,1\le a_i\le 32$。
对于$60\%$ 的数据，满足 $n \le 3000,1\le a_i\le 1024$。
对于$80\%$ 的数据，满足 $n\le 300000,1\le a_i\le 1048576$。
对于$100\%$ 的数据 ，满足 $1 \le n \le 5\times 10^5,1\le a_i< 2^{31}$ 。
时间限制:1s
空间限制:512MB
解题报告
题意理解
寻找一段区间，要求这段区间满足：
- 至少存在一个位置$k$，$a_k$可以整除这个区间所有的数$a_i$ 。
- 区间长度尽量长
这样的区间有很多个，因此题目要求
- 输出有多少个合法区间
- 这些合法区间的左端点。
$60pts$解析
拿到这道题目，我们发现，$60pts$的$n$取值范围很小，可以忍受$O(n^2)$的时间复杂度。
因此我们来对本题，进行初步分析。
首先我们发现，这个$k$一定在这个区间内，而且区间内，所有的数都是他的倍数。
那么，如果说，此时我确定了$k$这个坐标，那么，这个最长区间其实是可以确定下来了。
我们不妨设：
$$ 区间为[l,r] $$
那么根据题意
$$ [l,k-1]的数都是k的倍数 \\\\ [k+1,r]的数都是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\n",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$，这个答案呢？
因为
$$ R-L=(R-L+1)-1=Len-1 \quad Len为区间长度 $$
既然如此，那么现在的当务之急就是，如何判断存在这样的一个区间呢？
如果说
$$ gcd([L,R])=min([L,R]） $$
这里的意思是，一个区间的最大公约数$=$一个区间的最小数
那么这个区间肯定是合法的，反之必然。
两者互为充要条件。
这是为什么？
充分性证明
命题：区间合法是性质满足的充分条件
因为，我们发现，$a_k$一定是这个区间中的最小数。
否则，如果存在一个数，比他小，那么无法满足整除性质。
所以区间最小数必然是$a_k$
同样的，为什么最大公约数也必须是$a_k$呢？
因为，如果$a_k$是最小数，而最大公约数不可能大于最小数，只能小于等于它。
其次，又因为此时区间是合法的，所有数都是他的倍数，所以最大公约数是它。
所以充要性成立
必要性证明
命题：区间合法是性质满足的必要条件
因为:
$$ gcd([L,R])=min([L,R]） $$
区间所有数他们的最大公约数是$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\n",g[r].size(),r);
for(int s:g[r])
printf("%d ",s);
}
signed main()
{
init();
pre();
work();
return 0;
}
