【JZOJ6086】動态半平面交

Description

Solution

假設到 u u u不超過 d d d的點的權值分解質因數的質數集合為 p p p，答案就是要求 ∑ i = 1 ∣ p ∣ p i k i \sum\limits_{i=1}^{|p|} p_i^{k_i} i=1∑∣p∣​piki​​。

這個很不好處理，考慮把一個 p k p^k pk拆成 p , p 2 , p 3 , ⋯   , p k p,p^2,p^3,\cdots,p^k p,p2,p3,⋯,pk中顔色，每種顔色的貢獻都為 p p p，那麼題目轉化成為到 u u u不超過 d d d的點中顔色至少出現一次的貢獻積。那麼就是經典問題了，可以對每種顔色維護 d f s dfs dfs序，線上段樹上修改。至于這題，隻要按深度開可持久化線段樹即可，查詢相當于在 d e p u + d dep_u+d depu​+d的線段樹上查詢 u u u的子樹。

關于顔色的維護具體可以見這裡。

Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<set>
#include<vector>
#define fo(i,j,k) for(int i=j;i<=k;++i)
#define fd(i,j,k) for(int i=j;i>=k;--i)
#define rep(i,x) for(int i=ls[x];i;i=nx[i])
using namespace std;
typedef long long ll;
const int N=1e5+10,M=2e5+10,S=1e7+10,mo=998244353;
typedef multiset<int> :: iterator it;
int to[M],nx[M],ls[N],num=0;
void link(int u,int v){
	to[++num]=v,nx[num]=ls[u],ls[u]=num;
}
int bg[S],tt=0,tot=0;
multiset<int> cl[N*24];
int L[N],R[N],f[N][17],dep[N],z[N],n;
vector<int> dz[N];
int a[N];
int qpow(int x,int y){
	int s=1;
	for(;y;y>>=1,x=(ll)x*x%mo) if(y&1) s=(ll)s*x%mo;
	return s;
}
void pre(int x,int fr){
	z[L[x]=++tot]=x;
	f[x][0]=fr,dep[x]=dep[fr]+1;
	fo(i,1,16) f[x][i]=f[f[x][i-1]][i-1];
	rep(i,x) if(to[i]!=fr) pre(to[i],x);
	R[x]=tot;
}
int lca(int u,int v){
	if(dep[u]<dep[v]) swap(u,v);
	fd(i,16,0) if(dep[f[u][i]]>=dep[v]) u=f[u][i];
	if(u==v) return u;
	fd(i,16,0) if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
	return f[u][0];
}
int pr[S/15],sm[S];
int mx=0;
void pre0(){
	fo(i,2,mx){
		if(!sm[i]) sm[i]=i,pr[++pr[0]]=i;
		fo(j,1,pr[0]){
			int t=i*pr[j];
			if(t>mx) break;
			sm[t]=pr[j];
			if(i%pr[j]==0) break;
		}
	}
}
int d[50];
void find(int x){
	if(x==1) return;
	d[++d[0]]=sm[x],find(x/sm[x]);
}
int rt[N];
void mul(int &x,int y) {x=(ll)(!x?1:x)*y%mo;}
struct node{
	int v,l,r,s;
}tr[N*110];
int be[N*110];
int now;
void ins(int x,int t,int &v,int l=1,int r=n){
	if(be[v]!=now){
		tr[++tot]=tr[v],v=tot;
		be[v]=now;
	}
	mul(tr[v].s,t);
	if(l==r) return;
	int mid=(l+r)>>1;
	x<=mid?ins(x,t,tr[v].l,l,mid):ins(x,t,tr[v].r,mid+1,r);
}
int prod(int x,int y,int v,int l=1,int r=n){
	if(!v) return 1;
	if(l>=x && r<=y) return !tr[v].s?1:tr[v].s;
	int mid=(l+r)>>1,t=1;
	if(x<=mid) mul(t,prod(x,y,tr[v].l,l,mid));
	if(y>mid) mul(t,prod(x,y,tr[v].r,mid+1,r));
	return t;
}
int get(int x){
	if(!bg[x]){
		bg[x]=++tt;
		cl[tt].insert(0),cl[tt].insert(n+1);
	}
	return bg[x];
}
void modify(int t,int cc,int x){
	int col=get(cc),nt=qpow(t,mo-2);
	ins(L[x],t,rt[now]);
	cl[col].insert(L[x]);
	it pos=cl[col].find(L[x]);
	it p=pos,q=pos;--p,++q;
	if(*p && *q<=n) ins(L[lca(z[*p],z[*q])],t,rt[now]);
	if(*q<=n) ins(L[lca(z[*pos],z[*q])],nt,rt[now]);
	if(*p) ins(L[lca(z[*pos],z[*p])],nt,rt[now]);
}
void add(int x){
	d[0]=0,find(a[x]);
	fo(i,1,d[0]){
		int r=i,w=1,p=d[i];
		for(;r<d[0] && d[r+1]==p;++r);
		fo(j,i,r) w=(ll)w*p%mo,modify(p,w,x);
		i=r;
	}
}
int main()
{
	freopen("half.in","r",stdin);
	freopen("half.out","w",stdout);
	int tp;
	scanf("%d %d",&tp,&n);
	fo(i,1,n) scanf("%d",&a[i]),mx=max(mx,a[i]);
	fo(i,2,n){
		int u,v;
		scanf("%d %d",&u,&v);
		link(u,v),link(v,u);
	}
	pre0(),pre(1,0),tot=0;
	fo(i,1,n) dz[dep[i]].push_back(i);
	fo(i,1,n){
		now=i,rt[i]=rt[i-1];
		int o=dz[i].size();
		fo(j,0,o-1) add(dz[i][j]);
	}
	int q,ans=0;
	scanf("%d",&q);
	for(;q--;){
		int u,t;
		scanf("%d %d",&u,&t),u^=tp*ans,t^=tp*ans;
		ans=prod(L[u],R[u],rt[min(dep[u]+t,n)]);
		printf("%d\n",ans);
	}
}