前言
线段树练习赛 T1，最后一分钟调出来了。
所以我T2爆零。
题目
洛谷有翻译。
讲解
首先强制在线已经完全抑制了我们的想象力，而答案太大需要取模，我们只能思考对每个数质因数分解，然后求指数最大值的做法。
对于每个质因数我们都维护一棵线段树显然不现实，因为 (200000) 以内的质数已经多达 (17984) 个。
根据套路，我们将值域分块，(sqrt{200000}approx 447)， (447) 以内的质数只有 (86) 个。
对于这 (86) 个数，我们都开一棵线段树(或者一棵线段树维护 (86) 个值)，然后询问的时候查询区间最大值即可。
这个部分的时间复杂度为 (O(86nlog_2))，只要写得不算太丑应该没问题。
为了卡常，我还预处理了这 (86) 个数的幂，因为指数显然不会很大，所以这个幂可以预处理。
排除掉 (447) 以内的数之后，每个数只会存在至多一个大于 (447) 的质因数，这里有两个做法。
做法1
这是考试的时候的做法，时间复杂度不优，但是空间更优。
考虑分块。
对整个序列分块，预处理整块之间的最小公倍数，当然这里的序列已经不含 (447) 以内的因数了。
对于散块我们可以使用求区间不同数的经典套路：如果一个数的位置在询问区间中，而且前面与它相同的数的位置在询问区间外，那么才计入贡献。
由于散块在整块的前面和后面都有，所以要预处理前驱和后继，然后暴力判断即可。
时间复杂度为 (O((n+q)sqrt{n}))，空间为 (O(n))。
做法2
同样是做法1中的经典套路，对于每个数我们记录 ((pre_i,i)) 这样一组信息，放到线段树的叶子上，然后向上按 (pre_i) 单增进行归并排序。
每次询问时二分区间中最大的一个在询问区间左边的前驱，前缀积即为答案，所以归并的时候还要记录前缀积。
时间复杂度 (O(nlog^2_2n))，空间为 (O(nlog_2n))。
当然用主席树也行。
代码
考试代码
//12252024832524
#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define TT template<typename T>
using namespace std;
typedef long long LL;
const int MAXN = 200005;
const int MAXB = 450;//其实这里应该是sqrt(n)，大概是320
const int MOD = 1000000007;
int n,Q,tp;
int a[MAXN];
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
bool vis[MAXN];
int prime[MAXN],pn = -1,inv[MAXN];
void sieve(int x)
{
for(int i = 2;i <= x;++ i)
{
if(!vis[i]) prime[++pn] = i;
for(int j = 0;j <= pn && i * prime[j] <= x;++ j)
{
vis[i * prime[j]] = 1;
if(i % prime[j] == 0) break;
}
}
inv[0] = inv[1] = 1;
for(int i = 2;i <= x;++ i) inv[i] = 1ll * (MOD - MOD/i) * inv[MOD%i] % MOD;
}
int MAX[MAXN << 2][86],ri[86];
#define lc (x<<1)
#define rc (x<<1|1)
void Build(int x,int l,int r)
{
if(l == r)
{
a[l] = Read();
for(int i = 0;i < 86;++ i)
while(a[l] % prime[i] == 0) ++MAX[x][i],a[l] /= prime[i];
return;
}
int mid = (l+r) >> 1;
Build(lc,l,mid); Build(rc,mid+1,r);
for(int i = 0;i < 86;++ i)
MAX[x][i] = Max(MAX[lc][i],MAX[rc][i]);
}
void QQ(int x,int l,int r,int ql,int qr)
{
if(ql <= l && r <= qr)
{
for(int i = 0;i < 86;++ i) ri[i] = Max(ri[i],MAX[x][i]);
return;
}
int mid = (l+r) >> 1;
if(ql <= mid) QQ(lc,l,mid,ql,qr);
if(mid+1 <= qr) QQ(rc,mid+1,r,ql,qr);
}
map<int,int> m;
int mi[86][30];
int qpow(int x,int y)
{
int ret = 1;
while(y){if(y & 1) ret = 1ll * ret * x % MOD;x = 1ll * x * x % MOD;y >>= 1;}
return ret;
}
int lst;
int pre[MAXN],suf[MAXN];
int lcm[MAXB][MAXB];
bool ex[MAXN];
void solve2()
{
for(int i = 0;i < 86;++ i)
{
mi[i][0] = 1;
for(int j = 1;j < 30;++ j) mi[i][j] = 1ll * mi[i][j-1] * prime[i] % MOD;
}
Build(1,0,n-1);
m[1] = -1;
for(int i = 0;i <= pn;++ i) m[prime[i]] = -1;
for(int i = 0;i < n;++ i) pre[i] = m[a[i]],m[a[i]] = i;
m.clear();
m[1] = n;
for(int i = 0;i <= pn;++ i) m[prime[i]] = n;
for(int i = n-1;i >= 0;-- i) suf[i] = m[a[i]],m[a[i]] = i;
int B = ceil(sqrt(n));
for(int i = 0;i*B < n;++ i)
{
int l = i*B,cao = 1;
for(int j = i;j*B < n;++ j)
{
int r = Min(n-1,(j+1)*B-1);
for(int k = l;k <= r;++ k)
if(!ex[a[k]]) ex[a[k]] = 1,cao = 1ll * cao * a[k] % MOD;
lcm[i][j] = cao;
l = r+1;
}
for(int j = 0;j <= pn;++ j) ex[prime[j]] = 0;
}
Q = Read();
for(int i = 1;i <= Q;++ i)
{
int l = (lst + Read()) % n,r = (lst + Read()) % n;
if(l > r) swap(l,r);
lst = 1;
for(int j = 0;j < 86;++ j) ri[j] = 0;
QQ(1,0,n-1,l,r);
for(int j = 0;j < 86;++ j) lst = 1ll * lst * mi[j][ri[j]] % MOD;
int LID = l/B,RID = r/B;
if(LID+1 >= RID)
{
for(int j = l;j <= r;++ j)
if(a[j] > 1 && pre[j] < l)
lst = 1ll * lst * a[j] % MOD;
}
else
{
lst = 1ll * lst * lcm[LID+1][RID-1] % MOD;
int ll = l,rr = (LID+1)*B-1,xx = RID*B;
for(int j = ll;j <= rr;++ j)
if(a[j] > 1 && suf[j] >= xx)
lst = 1ll * lst * a[j] % MOD;
ll = RID*B; rr = r;
for(int j = ll;j <= rr;++ j)
if(a[j] > 1 && pre[j] < l)
lst = 1ll * lst * a[j] % MOD;
}
Put(lst,'
');
}
}
int main()
{
// freopen("lcm.in","r",stdin);
// freopen("lcm.out","w",stdout);
sieve(200000);
n = Read();
solve2();
return 0;
}
花絮
代码中的 solve2 函数是在线算法，solve1 是离线算法，只不过被我删掉了(考试的时候离线有60pts)。
也许我不打离线做法就有时间做T2了。