题目描述
小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.
这道题主要求的是最长区间长度,可以发现它是具有单调性的:对于一段区间,如果它是特殊区间,那么它一定有子区间是特殊区间。因此我们可以二分最长区间长度,对于每个二分出来的答案进行验证。那么怎么验证?可以发现特殊区间有几个很好的性质:1、ak一定是这段区间的最小值,因为如果有一个数ai比ak小,那ai一定不能被ak整除。2、ak一定是区间gcd,因为将所有ai都除以ak后,这段区间就变成了1,b1,b2……这些数gcd显然是1,再乘回ak后gcd就是ak了。那么只要比较一段区间最小值和gcd是否相同就能判断是否是特殊区间了。但如果暴力找区间最小值和区间gcd显然是不行的,因此要用ST表预处理出来g[i][j]和m[i][j]分别表示以j为起点往后2^i个数的gcd和最小值。再对于每个答案O(n)遍历所有起点判断并记录下来每个特殊区间的起点就OK了。每次验证是O(nlogn),总时间复杂度是O(n*(logn)^2)。
最后附上代码。
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cmath> using namespace std; int g[20][500010]; int m[20][500010]; int a[500010]; int l[500010]; int n; int L,R; int ans; int cnt; int q[500010]; int flag; int gcd(int x,int y) { if(x<y) { swap(x,y); } if(y!=0) { return gcd(y,x%y); } else { return x; } } bool check(int x) { cnt=0; for(int i=1;i+x-1<=n;i++) { int s=l[x]; if(gcd(g[s][i],g[s][i+x-(1<<s)])==min(m[s][i],m[s][i+x-(1<<s)])) { q[++cnt]=i; } } if(cnt!=0) { ans=max(ans,x); return true; } return false; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); g[0][i]=a[i]; m[0][i]=a[i]; } for(int i=1;(1<<i)<=n;i++) { for(int j=1;j+(1<<(i-1))<=n;j++) { g[i][j]=gcd(g[i-1][j],g[i-1][j+(1<<(i-1))]); m[i][j]=min(m[i-1][j],m[i-1][j+(1<<(i-1))]); } } for(int i=2;i<=n;i++) { l[i]=l[i>>1]+1; } L=1; R=n; while(L<R-1) { int mid=(L+R)>>1; if(check(mid)==true) { L=mid; } else { R=mid; } } bool o1=check(L); bool o2=check(R); bool o3=check(ans); printf("%d %d ",cnt,ans-1); for(int i=1;i<=cnt;i++) { if(flag==0) { printf("%d",q[i]); flag=1; } else { printf(" %d",q[i]); } } }