小生的（其实是老师带着写的）线段树：
#include <bits/stdc++.h>
#define LL long long
#define for_(i, a, b) for (int i = (a); i <= (b); i++)
#define _for(i, a, b) for (int i = (a); i >= (b); i--)
#define read() freopen("gcd.in", "r", stdin)
#define out() freopen("gcd.out", "w", stdout)
#define Mod int(1e9 + 7)
using namespace std;
const int N = 2e5 + 5;
int ans[1000005];
struct Node
{
int l, r;
int maxn;
} tre[N << 2];
int n, m;
int a[N];
int last[N];
vector<pair<int, int>> qu[N];
vector<int> divi[N];
void init()
{
for_(i, 1, N - 5)
{
for (int j = i; j <= N - 5; j += i)
{
divi[j].push_back(i);
}
}
}
void build(int l, int r, int pos)
{
tre[pos].l = l;
tre[pos].r = r;
tre[pos].maxn = 0;
if (l == r)
return;
int mid = l + r >> 1;
build(l, mid, pos << 1);
build(mid + 1, r, pos << 1 | 1);
}
void pushup(int pos)
{
tre[pos].maxn = max(tre[pos << 1].maxn, tre[pos << 1 | 1].maxn);
}
void modify(int pos, int L, int R, int val)
{
if(L > tre[pos].r || R < tre[pos].l)
return;
if(L <= tre[pos].l && tre[pos].r <= R)
{
tre[pos].maxn = max(val, tre[pos].maxn);
return;
}
modify(pos << 1, L, R, val);
modify(pos << 1 | 1, L, R, val);
pushup(pos);
}
int query(int pos, int L, int R)
{
if(L > tre[pos].r || R < tre[pos].l)
return 0;
if(L <= tre[pos].l && tre[pos].r <= R)
return tre[pos].maxn;
return max(query(pos << 1, L, R), query(pos << 1 | 1, L, R));
}
int main()
{
read();
out();
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for_(i, 1, n)
{
cin >> a[i];
}
cin >> m;
for_(i, 1, m)
{
int l, r;
cin >> l >> r;
qu[r].push_back({l, i});
}
init();
build(1, n, 1);
for_(i, 1, n)
{
for(auto d : divi[a[i]])
{
if(last[d] != 0)
{
modify(1, last[d], last[d], d);
}
last[d] = i;
}
for(auto x : qu[i])
{
int L = x.first;
int id = x.second;
ans[id] = query(1, L, i);
}
}
for_(i, 1, m) cout << ans[i] << endl;
return 0;
}
最后一个点太大，线段树时限3s任然TLE，各位大神求优化（快读快写我的同学们已经试过，优化300ms任然TLE，于是选择面向数据编程）