st表算法流程:
-
预处理:(ST)表在预处理阶段需要计算一个数组(f),(f_{i,j})表示区间(i ightarrow i+2^j-1)的最小值,也就是从(i)开始连续(2^j)个数的最小值。它可以通过倍增得到:(将(2^j)从中间平均分成两部分,每一部分都刚好是(2^{j-1}),而这就是一个子问题了)
(f_{i,j}=egin{cases}a_i&j=0\min(f_{i,j-1},f_{i+2^{j-},j-1})&j>0end{cases})
-
询问:现在考虑一个询问区间(s ightarrow y)内最小值的询问操作。首先我们可以求出满足(2^ileq y-x+1<2^{i+1})的(i),即(log2(y-x+1)),这样我们可以用两个长度为(2^i)的小区间覆盖询问的大区间
而长度为(2^i)的区间最小值我们在预处理阶段就已求出,因此区间(x ightarrow y)的最小值等于(min(f_{x,i}, f_{y-2^i+1,i}))。尽管这两个区间有交集,但对于最值来说并没有影响,这也就是 ST 表只适用于最值这类问题的原因
例题:
如果(x)能被区间内所有数整除,那么它一定是区间(gcd),且一定是区间最小值,所以只要判断区间(gcd)和区间最小值是否相同就可以知道这段区间是否满足条件
考虑二分答案,如果大区间符合要求,那么他包含的小区间一定也符合要求,满足单调性和局部取舍性,所以可以二分
code:
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int read(){
int x = 1,a = 0;char ch = getchar();
while (ch < '0'||ch > '9'){if (ch == '-') x = -1;ch = getchar();}
while (ch >= '0'&&ch <= '9'){a = a*10+ch-'0';ch = getchar();}
return x*a;
}
const int maxn = 1e6+10;
int n,a[maxn];
int st1[maxn][30],st2[maxn][30];
int gcd(int a,int b){
if (a%b == 0) return b;
gcd(b,a%b);
}
int ans[maxn],cnt,power[maxn];
bool check(int s){
for (int i = 1;i+s-1 <= n;i++){
int d = power[s];
int x = i,y = i+s-1;
int g = gcd(st2[x][d],st2[y-(1<<d)+1][d]);
int minn = min(st1[x][d],st1[y-(1<<d)+1][d]);
if (g == minn) return true;
}
return false;
}
int main(){
n = read();
for (int i = 1;i <= n;i++) a[i] = read();
power[0] = -1;
for (int i = 1;i <= n;i++) st1[i][0] = st2[i][0] = a[i],power[i] = power[i>>1]+1;
for (int j = 1;j <= 22;j++){
for (int i = 1;i+(1<<j)-1 <= n;i++){
st1[i][j] = min(st1[i][j-1],st1[i+(1<<j>>1)][j-1]);
st2[i][j] = gcd(st2[i][j-1],st2[i+(1<<j>>1)][j-1]);
}
}
int l = 1,r = n,mid = (l+r)>>1;
while (l<r){
mid = (l+r+1)>>1;
if (check(mid)) l = mid;
else r = mid-1;
}
for (int i = 1;i+l-1 <= n;i++){
int d = power[l];
int x = i,y = i+l-1;
int g = gcd(st2[x][d],st2[y-(1<<d)+1][d]);
int minn = min(st1[x][d],st1[y-(1<<d)+1][d]);
if (g == minn) cnt++,ans[cnt] = i;
}
printf("%d %d
",cnt,l-1);
for (int i = 1;i <= cnt;i++) printf("%d ",ans[i]);
return 0;
}