牛客挑战赛42 A
小睿睿的数列
https://ac.nowcoder.com/acm/contest/6944/A
分析
对于整个数列，因为每一个数只能被一个区间覆盖，所以考虑求出每个数的延伸范围。复杂度 。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 100;
int read() {int x;scanf("%d",&x);return x;}
int L[N],R[N],n,a[N],Ans,Max;
int main()
{
n = read();
for(int i = 1;i <= n;i++) {
a[i] = read();L[i] = R[i] = i;
}
for(int i = 1,l,r;i <= n;i = r + 1) {
l = i,r = i;
while((a[l-1]%a[i] == 0) && l > 1) l = L[l-1],L[i] = L[l];
while((a[r+1]%a[i] == 0) && r < n) r = R[r+1],R[i] = R[r];
if(R[i] - L[i] + 1 > Max) {Max = R[i] - L[i] + 1;Ans = 1;}
else if(R[i] - L[i] + 1 == Max) Ans ++;
}
printf("%d\n",Ans);
return 0;
} 
投递三维家等公司10个岗位