【CF1422F】Boring Queries 分块预处理+强制在线

George_Plover · 2021-05-15 21:04:18 · 题解

看了一下题解区的大佬们，无一例外的全部上了可持久化线段树，实在佩服。

鄙人不才，虽然早就做过了 HH的项链这道题，但是想题的时候还是没有自然的去想可持久化线段树的写法。

这里提供一个分块预处理的做法。总复杂度 O(222(n+q) +(n+q)\sqrt n ) 。

题意描述：

给出 n 个整数 1\le a_i \le 2\times 10^5 ，给出 q 组询问 [l,r] ，每次询问区间内数的 lcm ，强制在线，答案对 10^9+7 取模。 n,q \le 10^5 。

题目分析：

首先考虑到 lcm 非常大，必须在计算中取模，因此不能够直接的用区间求 lcm 的算法解决。所以考虑答案是质数幂次之积的形式，即 ans=p_1^{k_1}p_2^{k_2}\dots p_s^{k_s} 。
观察性质， a_i 范围很小，因此，对于 \sqrt{2\times 10^5} ≈ 447 以内的质因子，幂次才可能大于 1 ，其余的质因子的幂次要么是 1 ，要么是 0 。因此我们考虑分段处理。

做法：

第一部分

考虑处理 447 以内的质因子对答案的贡献，打表发现，这样的质因子一共有 86 个。到了这里，很多人就想用 86 个 ST 表来搞了。但我们暂时不慌，再考虑每个质因子 p_i 最高的幂次是 \log_{p_i}200000，所以我们可以继续打表，发现 447 以内的质因子对答案的贡献只有 \sum_{i=1}^{86} (log_{p_i}200000) ≈ 222 种状态。每个状态对应的值形如 p_i^{k} 。

因此，我们可以用一个 222 \times n 的数组 pre[222][n]，其中pre[][i]存下的是每个质因子的某个幂次在 [1,i] 范围内最后出现的位置。那么我们在求解这一段对答案的贡献的时候，可以直接枚举所有 86 个质因子，对每个质因子从大到小枚举幂次，找到第一个pre[][r]>=l 幂次，这就是这个质因子对答案的贡献。这样我们就可以 O(222) 处理每个询问的第一部分了。

第二部分

考虑第二部分，我们先把原来的 a_i 商掉所有 447 以内的质因子。那么接下来求解的贡献，其实就是区间 [l,r] 范围内出现过的数字的积。这里很多人就可持久化线段树上去搞了，但是我们考虑分块的做法。首先我们先要明白一点，假如我们已经处理出区间 [a,b] 的答案了，如果我们想拓展这个区间到 [a,b+1] 或 [a-1,b]，是可以 O(1) 做到的，只需要我们预处理出每个 a_i 左边最近一次出现的位置和右边最近一次出现的位置就可以了。因为利用预处理的值我们可以 O(1) 判断新拓展的值有没有在 [a,b] 出现过。既然如此，我们为什么不考虑分块呢？

每 \sqrt n 长度一个块，我们用一个二维数组 itv[L][R] 表示从第 L 块到第 R 块的区间的答案。这个二维数组的空间只有 O(n) ，并且我们可以 O(n\sqrt n) 预处理出这个二维数组。有了这个二维数组，我们就可以把询问区间 [l,r] 分为三段 [l,L-1],[L,R],[R+1,r] ，其中 [L,R] 是整块的一个区间，可以直接用预处理的 itv[][] 数组得到其贡献，然后再把这个区间向左右拓展，因此不满整块的 [l,L-1],[R+1,r] 长度都不超过 \sqrt n，因此我们只需要做 O(2\sqrt n) 次拓展即可求出区间 [l,r] 的贡献。

于是把上面两个过程结合起来，就可以以 O(222(n+q) +(n+q)\sqrt n ) 的时间复杂度和 O(222n) 的空间复杂度解决问题了。不需要用到可持久化线段树的技巧。

代码：

#include <map>
#include <cmath> 
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define MOD 1000000007
#define MAXN 220000
#define MAXC 230
#define LSQRT 87
#define BSIZE 350
using namespace std;
int n,m,a[MAXN];
int Div[MAXN],prime[MAXN],cnt;
int range[MAXN];
int base[MAXN];
int power[LSQRT][20];
int pre[MAXC][MAXN];
int loc[MAXN],lm[MAXN],rm[MAXN];
int itv[BSIZE][BSIZE];
bool vis[MAXN];
void get_p()
{
    for(int i=2;i<MAXN;i++)
    {
        if(!Div[i])
        {
            prime[++cnt]=i;
            Div[i]=i;
        }
        for(int j=1;j<=cnt&&prime[j]*i<MAXN;j++)
        {
            Div[prime[j]*i]=prime[j];
            if(prime[j]==Div[i])
                break;
        }
    }
}
void prepare_first()
{

    int sum=0;
    for(int i=1;i<LSQRT;i++)
    {
        range[i]=(log(200000)/log(prime[i]));
        base[i]=sum;
        sum+=range[i];
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<MAXC;j++)
            pre[j][i]=pre[j][i-1];
        for(int j=1;j<LSQRT;j++)
        {
            int cnt = 0;
            while(!(a[i]%prime[j]))
            {
                cnt++;
                a[i]/=prime[j];
            }
            if(cnt)
                pre[base[j]+cnt-1][i]=i;
        }
    }
    for(int i=1;i<LSQRT;i++)
    {
        int tmp=1;
        for(int j=1;j<20;j++)
        {
            tmp=1ll*tmp*prime[i]%MOD;
            power[i][j]=tmp;
        }
    }
}

void prepare_second()
{
    for(int i=1;i<=n;i++)
    {
        lm[i]=loc[a[i]];
        loc[a[i]]=i;
    }
    for(int i=1;i<MAXN;i++)loc[i]=n+1;
    for(int i=n;i>=1;i--)
    {
        rm[i]=loc[a[i]];
        loc[a[i]]=i;
    }

    for(int i=1;i<=n;i+=BSIZE)
    {
        memset(vis,0,sizeof(vis));
        int tmp=1;
        for(int j=i;j<=n;j++)
        {
            if(!vis[a[j]])
            {
                vis[a[j]]=1;
                tmp=1ll*tmp*a[j]%MOD;
            }
            if( !(j%BSIZE) || j==n)
            {
                itv[i/BSIZE][(j-1)/BSIZE]=tmp;
            }
        }
    }
}
int main()
{
    get_p();
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    prepare_first();
    prepare_second();
    scanf("%d",&m);
    int lst=0;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x=(lst+x)%n+1;
        y=(lst+y)%n+1;
        if(x>y)
            swap(x,y);
        lst=1;
        for(int i=1;i<LSQRT;i++)
        {
            for(int j=base[i]+range[i]-1;j>=base[i];j--)
            {
                if(pre[j][y]>=x)
                {
                    lst=1ll*lst*power[i][j-base[i]+1]%MOD;
                    break;
                }
            }
        }

        if(y-x+1 <= 2*BSIZE)
        {
            for(int i=x;i<=y;i++)
                if(lm[i]<x)
                    lst=1ll*lst*a[i]%MOD;
        }
        else
        {
            int L=(x-1)/BSIZE + 1,R=(y-1)/BSIZE - 1;
            lst=1ll*lst*itv[L][R]%MOD;
            for(int i=x;i<=L*BSIZE;i++)
                if(rm[i]>(R+1)*BSIZE)
                    lst=1ll*lst*a[i]%MOD;
            for(int i=(R+1)*BSIZE+1;i<=y;i++)
                if(lm[i]<x)
                    lst=1ll*lst*a[i]%MOD;
        }
        printf("%d\n",lst);
    }

    return 0;
}