P16829 题解
_buzhidao_
·
·
题解
本文中认为 $n,q,V$ 同阶。
首先树是假的，直接拍到序列上。
考虑经典性质：一个数至多有一个大于自己的平方根的质因子。
考虑分治，对于小于 $\sqrt n$ 的质因子，直接用势能线段树做就可以了。这部分别的题解讲的还是比较清楚的。这部分的时间复杂度是 $O(n\sqrt n)$ 的。
对于大于 $\sqrt n$ 的质因子，问题等价于维护一个序列，实现以下操作：
* 给定 $v$，将某个区间中所有不是 $v$ 的数变成 $0$。
* 查询某个区间中的所有数去重后的乘积。
考虑分块，取块长 $S=n^\frac23$。
对于所有**连续的块形成的区间**，用 `bitset` 维护这个区间中出现的数和这些数的乘积。这样的区间有 $O((n^\frac13)^2)=O(n^\frac23)$ 个。
利用**每个数只会被变成零一次**这个性质，容易实现以下操作：
* 找到某个修改操作中，应该被变成零的数。
* 将一个数变成零，并暴力修改所有受影响的信息。
* 查询某个区间中的所有数去重后的乘积。
于是我们就愉快地在 $O(n^\frac53)$ 的时间内解决了这个问题。
:::success[代码]
比较 dirty work。
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll mod=998244353;
constexpr int V=1e5;
bool npri[100005];
vector<int> smallpri,bigpri;
int toid[100005];
void init(){
npri[0]=npri[1]=1;
for(int i=2;i<=V/i;++i){
if(npri[i]) continue;
for(int j=i*i;j<=V;j+=i) npri[j]=1;
}
for(int i=2;i<=V;++i){
if(npri[i]) continue;
if(i<=V/i) toid[i]=smallpri.size(),smallpri.push_back(i);
else toid[i]=bigpri.size(),bigpri.push_back(i);
}
}
using num=vector<pair<int,int>>;
num cal(int x){
num res;
for(int p:smallpri){
if(x%p) continue;
res.push_back({p,0});
while(x%p==0) ++res.back().second,x/=p;
}
if(x>1) res.push_back({x,1});
return res;
}
ll inv[100005];
int n,q;
num s[100005];
int a[100005];
vector<int> t[100005];
int dfn[100005],dfncnt;
int tout[100005];
void dfs(int u,int fa){
dfn[u]=++dfncnt;
for(int v:t[u]) if(v!=fa) dfs(v,u);
tout[u]=dfncnt;
}
using value=pair<int,int>;
struct node{
int l,r;
value val;
node() = default;
node(int l,int r):l(l),r(r){}
};
#define lsp (p<<1)
#define rsp (p<<1|1)
class sgt{
private:
array<node,400005> t;
void pushup(int p);
public:
sgt() = default;
void buildt(int p,int l,int r);
void upd(int p,int u,int v);
value query(int p,int l,int r);
void chkmin(int l,int r,int v);
};
void sgt::pushup(int p){
t[p].val=max(t[lsp].val,t[rsp].val);
}
void sgt::buildt(int p,int l,int r){
t[p]={l,r};
if(l==r) return;
int mid=(l+r)>>1;
buildt(lsp,l,mid);
buildt(rsp,mid+1,r);
}
void sgt::upd(int p,int u,int v){
if(t[p].l==t[p].r) return (void)(t[p].val={v,u});
int mid=(t[p].l+t[p].r)>>1;
if(u<=mid) upd(lsp,u,v);
else upd(rsp,u,v);
pushup(p);
}
value sgt::query(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r) return t[p].val;
int mid=(t[p].l+t[p].r)>>1;
value res={0,0};
if(l<=mid) res=query(lsp,l,r);
if(r>mid) res=max(res,query(rsp,l,r));
return res;
}
void sgt::chkmin(int l,int r,int v){
value val=query(1,l,r);
if(val.first<=v) return;
upd(1,val.second,v);
chkmin(l,r,v);
}
sgt small[65];
constexpr int S=2000;
int o[100005];
int bi[100005];
int L[55],R[55];
bitset<9527> big[55][55];
ll pi[55][55];
int mark[55];
set<int> app[9527];
void remove(int i){
int p=o[i];
o[i]=0;
auto& app=::app[toid[p]];
app.erase(i);
if(app.empty()){
for(int b=1;b<=bi[n];++b){
for(int c=b;c<=bi[n];++c){
if(big[b][c][toid[p]]) pi[b][c]=pi[b][c]*inv[p]%mod;
big[b][c][toid[p]]=0;
}
}
return;
}
auto it=app.upper_bound(i);
int l,r;
if(it==app.begin()) l=0,r=*it;
else if(it==app.end()) l=*(--it),r=n+1;
else r=*it,l=*(--it);
int lb=bi[l]+1,rb=bi[r]-1;
for(int b=lb;b<=rb;++b){
for(int c=b;c<=rb;++c){
if(big[b][c][toid[p]]) pi[b][c]=pi[b][c]*inv[p]%mod;
big[b][c][toid[p]]=0;
}
}
}
void clear(int l,int r,int p){
if(bi[l]==bi[r]){
for(int i=l;i<=r;++i) if(o[i]&&o[i]!=p) remove(i);
return;
}
for(int i=l;i<=R[bi[l]];++i) if(o[i]&&o[i]!=p) remove(i);
for(int i=L[bi[r]];i<=r;++i) if(o[i]&&o[i]!=p) remove(i);
for(int b=bi[l]+1;b<=bi[r]-1;++b){
if(!mark[b]){
for(int i=L[b];i<=R[b];++i) if(o[i]&&o[i]!=p) remove(i);
mark[b]=p;
}
else if(mark[b]!=-1&&mark[b]!=p){
for(int i=L[b];i<=R[b];++i) if(o[i]&&o[i]!=p) remove(i);
mark[b]=-1;
}
}
}
bool vis[9527];
int main(){
ios::sync_with_stdio(0);
init();
inv[1]=1;
for(int i=2;i<=1e5;++i) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
cin>>n>>q;
for(int u=1;u<=n;++u) cin>>a[u];
for(int i=1;i<n;++i){
int u,v;
cin>>u>>v;
t[u].push_back(v),t[v].push_back(u);
}
dfs(1,0);
for(int u=1;u<=n;++u) s[dfn[u]]=cal(a[u]);
for(int i=0;i<65;++i) small[i].buildt(1,1,n);
for(int i=1;i<=n;++i){
bi[i]=(i-1)/S+1;
if(bi[i]!=bi[i-1]) L[bi[i]]=i;
R[bi[i]]=i;
}
bi[n+1]=bi[n]+1;
for(int i=1;i<=n;++i){
for(auto [p,c]:s[i]){
if(p<=smallpri.back()) small[toid[p]].upd(1,i,c);
else app[toid[p]].insert(i),big[bi[i]][bi[i]][toid[p]]=1,o[i]=p;
}
}
for(int b=1;b<=bi[n];++b){
for(int c=b+1;c<=bi[n];++c){
big[b][c]=big[b][c-1]|big[c][c];
}
}
for(int b=1;b<=bi[n];++b){
for(int c=b;c<=bi[n];++c){
pi[b][c]=1;
for(int i=0;i<9527;++i) if(big[b][c][i]) pi[b][c]=pi[b][c]*bigpri[i]%mod;
}
}
while(q--){
int op;
cin>>op;
if(op==1){
int u,x;
cin>>u>>x;
int i=0;
bool fl=1;
for(auto [p,c]:cal(x)){
if(p<=smallpri.back()){
while(i<toid[p]) small[i++].chkmin(dfn[u],tout[u],0);
small[toid[p]].chkmin(dfn[u],tout[u],c);
i=toid[p]+1;
}
else clear(dfn[u],tout[u],p),fl=0;
}
while(i<65) small[i++].chkmin(dfn[u],tout[u],0);
if(fl) clear(dfn[u],tout[u],bigpri[0]),clear(dfn[u],tout[u],bigpri[1]);
}
else{
int u;
cin>>u;
int l=dfn[u],r=tout[u];
ll ans=1;
for(int i=0;i<65;++i){
int c=small[i].query(1,l,r).first;
while(c--) ans=ans*smallpri[i]%mod;
}
if(bi[r]-bi[l]<=1){
for(int i=l;i<=r;++i) if(o[i]&&!vis[toid[o[i]]]) ans=ans*o[i]%mod,vis[toid[o[i]]]=1;
for(int i=l;i<=r;++i) if(o[i]) vis[toid[o[i]]]=0;
}
else{
auto& bs=big[bi[l]+1][bi[r]-1];
ans=ans*pi[bi[l]+1][bi[r]-1]%mod;
for(int i=l;i<=R[bi[l]];++i) if(o[i]&&!vis[toid[o[i]]]&&!bs[toid[o[i]]]) ans=ans*o[i]%mod,vis[toid[o[i]]]=1;
for(int i=L[bi[r]];i<=r;++i) if(o[i]&&!vis[toid[o[i]]]&&!bs[toid[o[i]]]) ans=ans*o[i]%mod,vis[toid[o[i]]]=1;
for(int i=l;i<=R[bi[l]];++i) if(o[i]) vis[toid[o[i]]]=0;
for(int i=L[bi[r]];i<=r;++i) if(o[i]) vis[toid[o[i]]]=0;
}
cout<<ans<<endl;
}
}
return 0;
}
```
:::