rt，这是我的线段树（比赛打的依托使）

#include<bits/stdc++.h>
#define int long long
#define pb emplace_back
#define min(x,y) (x<y?x:y)
#define lid (id << 1)
#define rid (id << 1 | 1)
using namespace std;
int n;
int a[500005];
struct node {
	int l,r,val = 1e9,gcd;
}tr[2000005];
vector<int>vec;
void pushup(int id){
	tr[id].val = min(tr[lid].val,tr[rid].val);
	tr[id].gcd = __gcd(tr[lid].gcd,tr[rid].gcd);
}
void build(int id,int l,int r) {
	tr[id].l = l,tr[id].r = r;
	if(l == r) {
		tr[id].val = tr[id].gcd = a[l];
		return ;
	}
	int mid = (l + r) / 2;
	if(l <= mid) build(lid,l,mid);
	if(r > mid) build(rid,mid + 1,r); 
	pushup(id);
}
int query(int id,int l,int r) {
	if(tr[id].l >= l && tr[id].r <= r) return tr[id].val;
	int mid = (tr[id].l + tr[id].r) >> 1,ans = 1e18;
	if(l <= mid) ans = min(ans,query(lid,l,r));
	if(r > mid) ans = min(ans,query(rid,l,r));
	pushup(id);
	return ans;
}
int queryg(int id,int l,int r) {
	if(tr[id].l >= l && tr[id].r <= r) return tr[id].gcd;
	int mid = (tr[id].l + tr[id].r) >> 1,ans = 0;
	if(l <= mid) ans = queryg(lid,l,r);
	if(r > mid) ans = __gcd(ans,queryg(rid,l,r));
	pushup(id);
	return ans;
}
pair<int,int> check(int nowlen) {
	vec.clear();
	int cur = 0;
	for(int l = 1;l <= n - nowlen;++l){
		int r = l + nowlen;
		if(query(1,l,r) == queryg(1,l,r)) {++cur;vec.pb(l);}
	}
	return make_pair(cur > 0,cur);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(int i = 1;i <= n;++i) cin >> a[i];
	build(1,1,n);
	int gs = 0,cost = 0;
	int L = 0,R = n,ans = 0;
	while(L <= R) {
		int mid = L + R >> 1;
		if(check(mid).first) cost = mid,L = mid + 1;
		else R = mid - 1;
	}
	cout << check(cost).second << " " << cost << '\n';
	for(auto x : vec) cout << x << " ";
	return 0;
}

然后他成功的拿到了TLE30分的好成绩，但是我本地测试，在 $n < 5000$ 时计算次数比暴力少了100倍，为什么跑出来速度比暴力还慢？