Codeforces 1422F - Boring Queries（树套树）
upd on 2021.9.5：昨天的那个版本被 2-tower 卡爆了，故今天重发一个。
没往“每个数最多只有一个 \(>\sqrt{x}\) 的质因子”这个性质的蒟蒻来一发特别暴力的解法。
首先看到这个强制在线显然无法用 cdq 分治或者扫描线一类离线算法维护，因此考虑主席树或者树套树这一类在线算法。注意到对于一个质因子 \(p\)，显然 \(p\) 对一段区间的贡献就是 \(p^\text{maxc}\)，其中 \(\text{maxc}\) 表示区间 \([l,r]\) 中 \(p\) 次数的最大值。这个最大值显然不好维护，因此转化为对于每个数 \(p\) 的次数 \(p^c\)，它会对哪些区间产生贡献，根据笛卡尔树那一套理论，满足 \([l,r]\) 中 \(p\) 次数的最大值刚好为 \(c\) 的区间左端点形成一个区间 \([L_l,R_l]\)，右端点也形成一个区间 \([L_r,R_r]\)，因此对于 \(l\in[L_l,R_l],r\in[L_r,R_r]\)，\([l,r]\) 区间的答案应乘上 \(p^c\)。\(L_l,R_l,L_l,R_r\) 可以单调栈求，当然也可以从小到大将所有 \(c\) 插入 set 中然后在 set 中用 lower_bound 之类的东西求得。由于只有 \(c\ne 0\) 的 \(c\) 是有意义的，而对于所有 \(p\)，有意义的 \(c\) 的个数之和应为所有 \(a_i\) 质因子个数之和，而这显然不超过 \(\max\{\omega(n)\}·n\approx 7n\)，因此这样复杂度是 \(\mathcal O(7n)\) 或 \(\mathcal O(7n\log n)\)，在可接受范围内。
接下来考虑怎样计算答案。显然经过我们这么一分析，所有贡献都可以转化为以下形式：初始有一个全为 \(1\) 的矩阵 \(a\)，有若干次操作：对于 \(i\in[l_1,r_1],j\in[l_2,r_2],a_{i,j}\leftarrow a_{i,j}·v\)，求 \(a_{l,r}\)。看到这个设问一眼树套树，直接树套树大概是 \(7n·\log^2n\)，空间和时间都很危，我第一次提交大约是 TLE #21。考虑加一点小小的优化，根据复杂度平衡的思想，我们设一个阈值 \(B\)（\(30\sim 50\)），那么对于 \(\le B\) 的质因子，有意义的 \(c\) 的个数可能很多，此时直接 ST 表维护最大值是 \(n\log n\) 的，反而优于树套树的 2log，因此考虑对 \(\le B\) 的质因子每个建一个 ST 表，然后每次询问这些质因子的贡献就暴力遍历即可。
const int MAXN=1e5;
const int MAXV=2e5;
const int MAXP=MAXN<<8;
const int LOG_N=17;
const int MOD=1e9+7;
int n,qu,a[MAXN+5];
int pr[MAXV/6+5],prcnt=0,mnp[MAXV+5];
bitset<MAXV+5> vis;
vector<pii> ps[MAXV+5];
void sieve(int n){
for(int i=2;i<=n;i++){
if(!vis[i]) pr[++prcnt]=i,mnp[i]=i;
for(int j=1;j<=prcnt&&pr[j]*i<=n;j++){
vis[pr[j]*i]=1;mnp[pr[j]*i]=pr[j];
if(i%pr[j]==0) break;
}
}
}
int qpow(int x,int e){
int ret=1;
for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;
return ret;
}
struct node{int ch[2],val;} s[MAXP+5];
int rt[MAXN+5],ncnt=0;
void pushup(int k){s[k].val=1ll*s[s[k].ch[0]].val*s[s[k].ch[1]].val%MOD;}
void insert_in(int &k,int l,int r,int p,int v){
if(!k) k=++ncnt,s[k].val=1;
if(l==r) return s[k].val=1ll*s[k].val*v%MOD,void();
int mid=l+r>>1;
if(p<=mid) insert_in(s[k].ch[0],l,mid,p,v);
else insert_in(s[k].ch[1],mid+1,r,p,v);
pushup(k);
}
void insert(int x,int l,int r,int v){
int iv=qpow(v,MOD-2);
for(int i=x;i<=n;i+=(i&(-i))){
insert_in(rt[i],1,n,l,v);
if(r!=n) insert_in(rt[i],1,n,r+1,iv);
}
}
int query_in(int k,int l,int r,int ql,int qr){
if(!k) return 1;if(ql<=l&&r<=qr) return s[k].val;
int mid=l+r>>1;
if(qr<=mid) return query_in(s[k].ch[0],l,mid,ql,qr);
else if(ql>mid) return query_in(s[k].ch[1],mid+1,r,ql,qr);
else return 1ll*query_in(s[k].ch[0],l,mid,ql,mid)*query_in(s[k].ch[1],mid+1,r,mid+1,qr)%MOD;
}
int query(int x,int y){
int ret=1;
for(;x;x&=(x-1)) ret=1ll*ret*query_in(rt[x],1,n,1,y)%MOD;
return ret;
}
void add(int l1,int r1,int l2,int r2,int v){
// printf("%d %d %d %d %d\n",l1,r1,l2,r2,v);
insert(l1,l2,r2,v);if(r1^n) insert(r1+1,l2,r2,qpow(v,MOD-2));
}
int st[11][MAXN+5][LOG_N+2];
int query_st(int x,int l,int r){
int k=31-__builtin_clz(r-l+1);
return max(st[x][l][k],st[x][r-(1<<k)+1][k]);
}
int main(){
scanf("%d",&n,&qu);sieve(MAXV);s[0].val=1;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
int tmp=a[i];
while(tmp^1){
int p=mnp[tmp],cnt=0;
while(tmp%p==0) tmp/=p,cnt++;
ps[p].pb(mp(cnt,i));
}
}
for(int i=1;i<=10;i++){
for(pii p:ps[pr[i]]) st[i][p.se][0]=p.fi;
for(int j=1;j<=LOG_N;j++) for(int k=1;k+(1<<j)-1<=n;k++)
st[i][k][j]=max(st[i][k][j-1],st[i][k+(1<<j-1)][j-1]);
}
for(int i=31;i<=MAXV;i++) if(!ps[i].empty()){
sort(ps[i].begin(),ps[i].end());
reverse(ps[i].begin(),ps[i].end());
set<int> st;st.insert(0);st.insert(n+1);
for(pii p:ps[i]){
st.insert(p.se);
set<int>::iterator it=st.find(p.se);
int pre=*--it,nxt=*++ ++it;
// printf("%d %d\n",pre,nxt);
add(pre+1,p.se,p.se,nxt-1,qpow(i,p.fi));
}
} scanf("%d",&qu);int pre=0;
while(qu--){
int x,y;scanf("%d%d",&x,&y);
x=(x+pre)%n+1;y=(y+pre)%n+1;
if(x>y) swap(x,y);
// printf("%d %d\n",x,y);
pre=query(x,y);
for(int i=1;i<=10;i++) pre=1ll*pre*qpow(pr[i],query_st(i,x,y))%MOD;
printf("%d\n",pre);
}
return 0;
}手机扫一扫
移动阅读更方便
你可能感兴趣的文章