CF1422F Boring Queries 题解

根号分治+ST表+主席树区间出现过的数的乘积

Statement

给定一个长度为 \(n\) 的序列 \(a\) 以及 \(q\) 次询问 。

每次询问包含 \(2\) 个整数 \(l,r\) ，你需要求出区间 \([l,r]\) 的最小公倍数对 \(10^9 + 7\) 取模的结果。

询问强制在线 。

数据范围： \(1\leq n,q\leq 10^5,1 \leq a_i\leq 2\cdot 10^5,1\leq x,y \leq 10^5\)

Solution

题目即是求 \(\prod p_i^{c_i}\) ,\(c_i=\max\{a_{x,i}\}\) ,\(a_{x,i}\) 表示 \(a_x\) 的素数 \(p_i\) 的次数

看到值域 \(\le 10^5\) ，考虑值域分块

在 \(\sqrt{10^5}\) 的范围内只有 \(87\) 个素数，所以我们可以开 \(87\) 个 ST 表解决

然后我们把 \(a[i]\) 中小于 \(\sqrt{10^5}\) 的素因子全部除掉，则 \(a[i]\) 只能是 \(1\) 或者单个 \(>\sqrt{10^5}\) 的素数

问题就变成了算区间出现过的数的乘积，可以参照 HH 的项链 中的主席树做法

设 \(pre_i\) 表示值 \(i\) 前一次出现的位置，询问 \(l,r\) 即是：\(\prod [pre_i

那么我们搞一个主席树，\(root[k]\) 存储 \(pre_i\le k\) 的信息

发现从 \(root[k-1]\) 到 \(root[k]\) 仅仅可能增加一个位置，所以确实可以主席树

特别的，\(root[0]\) 记录每个数第一次出现的位置的信息，方便询问

时间复杂度 \(O(能过)\)

Code

注意到 ST 表空间有点卡，开成 \(char\)

#include
#define ls lc[rt]
#define rs rc[rt]
#define mid ((l+r)>>1)
#define swap(x,y) x^=y^=x^=y
using namespace std;
typedef long long ll;
const int N = 2e5+5;
const int K = 450;
const int mod = 1e9+7;

int read(){
    int s=0,w=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch))s=s*10+(ch^48),ch=getchar();
    return s*w;
}

int a[N],prime[100],lc[N*18],rc[N*18];
int pos[N<<1],b[N],Log[N],rot[N];
char f[90][N][18];
ll t[N*18],pw[100][21];
int n,q,cnt,siz;
bool vis[K];

void getprime(int n){
    for(int i=2;i<=n;++i){
        if(!vis[i])prime[++cnt]=i;
        for(int j=1;j<=cnt&&i*prime[j]<=n;++j){
            vis[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
}
int ask(int l,int r,int k){
    int t=Log[r-l+1];
    return max(f[k][l][t],f[k][r-(1<>1]+1;
    for(int k=1;k<=cnt;++k)for(int i=1;(1<r)swap(l,r);
        for(int i=1;i<=cnt;++i)
            (lastans*=pw[i][ask(l,r,i)])%=mod;
        lastans=(lastans*query(1,n,rot[l-1],l,r))%mod;
        printf("%lld\n",lastans);
    }
    return 0;
}
/*
3
2 3 5
4
1 3
3 3
2 3
2 3
*/