題目

描述 :

給出強(qiáng)制在線參數(shù)\(k\),樹的大小\(n\)，和每個點(diǎn)的點(diǎn)權(quán)\(a_i\);

有\(m\)個詢問，每個詢問是$u ,d $ 的形式；

表示詢問\(u\)為根的子樹中，和\(u\)的距離不超過\(d\)的點(diǎn)的點(diǎn)權(quán)\(lcm\)；

范圍：

$k \in { 0,1 } ?,?1 \le n ?, q \le 100000 ?, ?a_i \le 10000000 $;

題解

• \(lcm\)不太好合并，首先一定是找到一種合理的方式去表示\(lcm\)；

• 考慮每個因子\(p\)，如果存在將\(p,p^2,p^3,\cdots\)看成不同的顏色，每種顏色存在的貢獻(xiàn)是將答案乘以\(p\);

• 對于每一種顏色，我們只需要維護(hù)一個樹鏈并即可；

• 對每個顏色維護(hù)一個\(set\)，用來維護(hù)插入一個點(diǎn)樹鏈并的修改；

• 對于非強(qiáng)制在線的情況，只需要將詢問按\(dep[u]+d\)排序，線段樹維護(hù)單點(diǎn)修改子樹查詢；

• 強(qiáng)制在線將線段樹可持久化就好了；

• 時間復(fù)雜度和空間復(fù)雜度：\(O(n \ log \ n \ log \ a_i)\) ;

  #include<bits/stdc++.h> #define pb push_back #define mod 998244353 #define ll long long using namespace std; const int N=100010,M=10000010; int n,m,k,a[N],b[N],o=1,hd[N],idx,st[N],ed[N],id[N],dep[N]; int f[N<<1][20],lg[N<<1],pos[N<<1],bin[20],idx2; int sz,rt[N],mul[N*600],ls[N*600],rs[N*600]; int vis[M],pr[M],pt,mn[M]; struct Edge{int v,nt;}E[N<<1]; set<int>s[N*30]; set<int>::iterator I,I1,I2; map<int,int>hsh; char gc(){static char*p1,*p2,s[1000000];if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);return(p1==p2)?EOF:*p1++; } int rd(){int x=0;char c=gc();while(c<'0'||c>'9')c=gc();while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc();return x; } void adde(int u,int v){E[o]=(Edge){v,hd[u]};hd[u]=o++;E[o]=(Edge){u,hd[v]};hd[v]=o++; } void pre(){mn[1]=1;for(int i=2;i<=1e7;++i){if(!vis[i])mn[pr[++pt]=i]=i;for(int j=1,t;j<=pt&&i*pr[j]<=1e7;++j){vis[t=i*pr[j]]=1;mn[t]=pr[j];if(i%pr[j]==0)break;}} } void dfs(int u,int fa){f[pos[u]=++idx2][0]=u;id[st[u]=++idx]=u;dep[u]=dep[fa]+1;for(int i=hd[u];i;i=E[i].nt){int v=E[i].v;if(v==fa)continue;dfs(v,u);f[++idx2][0]=u;}ed[u]=idx; } int Min(int x,int y){return dep[x]<dep[y]?x:y;} void init(){lg[0]=-1;for(int i=1;i<=idx2;++i)lg[i]=lg[i>>1]+1;for(int i=bin[0]=1;i<=18;++i)bin[i]=bin[i-1]<<1;for(int i=1;i<=18;++i)for(int j=1;j+bin[i]-1<=idx2;++j){f[j][i]=Min(f[j][i-1],f[j+bin[i-1]][i-1]);} } int lca(int u,int v){int x=pos[u],y=pos[v]; if(x>y)swap(x,y);int t=lg[y-x+1];return Min(f[x][t],f[y-bin[t]+1][t]); } bool cmp(const int&x,const int&y){return dep[x]<dep[y];} int get(int x){if(!hsh[x])return hsh[x]=++idx;return hsh[x]; } int pw(int x,int y){int re=1;while(y){if(y&1)re=(ll)re*x%mod;y>>=1;x=(ll)x*x%mod;}return re; } void ins(int&k,int lst,int l,int r,int x,int y){mul[k=++sz]=(ll)mul[lst]*y%mod;ls[k]=ls[lst],rs[k]=rs[lst];if(l==r)return; int mid=l+r>>1;if(x<=mid)ins(ls[k],ls[lst],l,mid,x,y);else ins(rs[k],rs[lst],mid+1,r,x,y); } int query(int k,int l,int r,int x,int y){if(l==x&&r==y)return mul[k];int mid=l+r>>1;if(y<=mid)return query(ls[k],l,mid,x,y);else if(x>mid)return query(rs[k],mid+1,r,x,y);else return (ll)query(ls[k],l,mid,x,mid)*query(rs[k],mid+1,r,mid+1,y)%mod; } int main(){freopen("half.in","r",stdin);freopen("half.out","w",stdout);pre();k=rd();n=rd();for(int i=1;i<=n;++i)a[i]=rd(),b[i]=i;for(int i=1;i<n;++i)adde(rd(),rd());dfs(1,0);init();sort(b+1,b+n+1,cmp);mul[0]=1;idx=0;for(int i=1;i<=n;++i){int u=b[i],d=dep[u],tmp=a[u];rt[d]=rt[dep[b[i-1]]];while(tmp!=1){int x=mn[tmp],ix=pw(x,mod-2),y,z=1;while(tmp%x==0&&(tmp/=x)){y=get(z*=x);s[y].insert(st[u]);I=s[y].lower_bound(st[u]);I1=I;if(I!=s[y].begin())--I1;I2=I;++I2;ins(rt[d],rt[d],1,n,st[u],x);int u1=0,u2=0,t;if(I!=s[y].begin()){u1=id[*I1];t=lca(u1,u); ins(rt[d],rt[d],1,n,st[t],ix);}if(I2!=s[y].end()){u2=id[*I2];t=lca(u2,u); ins(rt[d],rt[d],1,n,st[t],ix);}if(u1&&u2){t=lca(u1,u2);ins(rt[d],rt[d],1,n,st[t],x);}}}}for(int i=dep[b[n]]+1;i<=n;++i)rt[i]=rt[i-1];m=rd();int ans=0;for(int i=1,u,d;i<=m;++i){u=rd()^(k*ans);d=min(n,dep[u]+rd()^(k*ans));ans=query(rt[d],1,n,st[u],ed[u]);printf("%d\n",ans);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Paul-Guderian/p/10602136.html

總結(jié)

以上是生活随笔為你收集整理的【纪中集训2019.3.26】动态半平面交的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。