【2018/11/02测试T1】优美的序列

【题目】

传送门

【分析】

60 pts：

枚举每个数，暴力找出左边和右边第一个不是它倍数的数 $l$l 和 $r$r，那么 $l+1$l+1 到 $r-1$r−1 就是符合条件的，暴力统计就行了

不过要注意有些区间会重复计算，要去重啊（我就死在这了）

100 pts：

注意到要找的东西是可以用单调栈来做的，这样就把 $n^2$n2 降到 $n$n 了

【代码】

#include<stack>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 500005
using namespace std;
stack<int>stk;
int a[N],L[N],R[N],rec[N];
bool vis[N];
int main()
{
//	freopen("sequence.in","r",stdin);
//	freopen("sequence.out","w",stdout);
	int n,i;
	scanf("%d",&n);
	for(i=1;i<=n;++i)
	  scanf("%d",&a[i]);
	for(i=1;i<=n;++i)
	{
		while(!stk.empty()&&a[i]%a[stk.top()])  R[stk.top()]=i-1,stk.pop();
		stk.push(i);
	}
	while(!stk.empty())  R[stk.top()]=n,stk.pop();
	for(i=n;i;--i)
	{
		while(!stk.empty()&&a[i]%a[stk.top()])  L[stk.top()]=i+1,stk.pop();
		stk.push(i);
	}
	while(!stk.empty())  L[stk.top()]=1,stk.pop();
	int len,Max=0,num=0;
	for(i=1;i<=n;++i)
	{
		len=R[i]-L[i];
		if(Max<len)  Max=len,rec[num=1]=L[i],vis[L[i]]=true;
		else  if(Max==len&&!vis[L[i]])  rec[++num]=L[i],vis[L[i]]=true;
	}
	printf("%d %d\n",num,Max);
	sort(rec+1,rec+num+1);
	for(i=1;i<=num;++i)
	  printf("%d ",rec[i]);
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}