G-Yu Ling(Ling YueZheng) and Colorful Tree

HOWARLI題解

大致做法就是首先考慮哪些修改可能影響詢問，當修改點權是詢問的倍數時才可能影響詢問。于是考慮把他們放在一起。

首先每次枚舉每種詢問的倍數，把這些修改和當前詢問放在一起，由于每次考慮的是該點到根節點路徑上的點，對于每個點的點權的修改僅僅影響的子樹節點的詢問。于是將單點修改$\to$子樹修改，鏈詢問$\to$單點詢問。

于是每次修改轉化成$[{\text{dfn}}_u,{\text{dfn}}_u+{\text{sz}}_u?1]$添加一個$[x,{\text{dis}}_u]$即可以表示成插入$\{\text{id},{\text{dfn}}_u\to {\text{dfn}}_u+{\text{sz}}_u?1,x\}={\text{dis}}_u$

于是詢問的問題轉化成${\text{dfn}}_u$處詢問$[[l,r],\max \{{\text{dis}}_u\}]$可以表示成詢問$\max \{\{\text{id},{\text{dfn}}_u,l\to r\}=\text{dis}\}$

現在相當于有三維$[\text{id},\text{dfn},\text{val}]$，即空間上的一個點，點權是$\text{dis}$，顯然可以樹套樹或者cdq分治。

分析一下就可以知道上述求的$\max \text{dis}$一定是離$u$最近的。
下面代碼用cdq分治。不過wtcl還沒調出來~~

#include<bits/stdc++.h> using namespace std; using ll=long long; template <class T=int> T rd() {T res=0;T fg=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') fg=-1;ch=getchar();}while( isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=getchar();return res*fg; } const int N=110005; int h[N],e[2*N],ne[2*N],idx; ll w[2*N]; void add(int a,int b,ll c){e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;}int n,m; struct node1 {int op,u,x;int l,r; }q[N]; struct node2 {int op,id;int t,l,r;ll x; }q0[N<<1]; int dfn[N],timestamp; ll dis[N]; int sz[N]; void dfs(int u,int fa) {dfn[u]=++timestamp;sz[u]=1;for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(v==fa) continue;dis[v]=dis[u]+w[i];dfs(v,u);sz[u]+=sz[v];} } vector<int> V0[N],V1[N]; ll v[N<<2]; ll ans[N]; void modify(int u,int l,int r,int pos,ll x) {if(l==r) return v[u]=x,void();int mid=l+r>>1;if(pos<=mid) modify(u<<1,l,mid,pos,x);else modify(u<<1|1,mid+1,r,pos,x);v[u]=max(v[u<<1],v[u<<1|1]); } ll query(int u,int l,int r,int L,int R) {if(L<=l&&r<=R) return v[u];int mid=l+r>>1;ll c=-1;if(L<=mid) c=max(c,query(u<<1,l,mid,L,R));if(R>mid)c=max(c,query(u<<1|1,mid+1,r,L,R));return c; } void solve(int l,int r) {if(l>=r) return;int mid=l+r>>1;solve(l,mid),solve(mid+1,r);int i=l;for(int j=mid+1;j<=r;j++){while(i<=mid&&q0[i].t<=q0[j].t){if(q0[i].op==0) modify(1,1,n,q0[i].l,q0[i].x);i++;}if(q0[j].op==1) ans[q0[j].id]=max(ans[q0[j].id],query(1,1,n,q0[j].l,q0[j].r));}while(i>l) {--i;if(q0[i].op==0) modify(1,1,n,q0[i].l,-1);}inplace_merge(q0+l,q0+mid+1,q0+r+1,[](const node2&a,const node2&b){return a.t<b.t;}); } int main() {n=rd(),m=rd();memset(h,-1,sizeof h);memset(v,-1,sizeof v);memset(ans,-1,sizeof ans);for(int i=1;i<n;i++) {int u=rd(),v=rd(),c=rd();add(u,v,c),add(v,u,c);}for(int i=1;i<=m;i++){q[i].op=rd();q[i].u=rd();if(q[i].op) {q[i].l=rd(),q[i].r=rd(),q[i].x=rd();V1[q[i].x].push_back(i);}else {q[i].x=rd();V0[q[i].x].push_back(i);}}dfs(1,0);int cnt;for(int i=1;i<=n;i++){if(V1[i].empty()) continue;cnt=0;for(int j=i;j<=n;j+=i){for(int k:V0[j]){int u=q[k].u;q0[++cnt]={0,k,dfn[u],j,j,dis[u]};q0[++cnt]={0,k,dfn[u]+sz[u],j,j,-1};}}if(!cnt) continue;for(int k:V1[i]){int u=q[k].u,l=q[k].l,r=q[k].r;q0[++cnt]={1,k,dfn[u],l,r};}sort(q0+1,q0+1+cnt,[](const node2& a,const node2 &b){return a.id<b.id||a.id==b.id&&a.op<b.op;});solve(1,cnt);}for(int i=1;i<=m;i++){if(q[i].op==0) continue;if(ans[i]==-1)puts("Impossible!");elseprintf("%lld\n",dis[q[i].u]-ans[i]);} }

上面代碼有大問題

#include<bits/stdc++.h> using namespace std; using ll=long long; template <class T=int> T rd() {T res=0;T fg=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') fg=-1;ch=getchar();}while( isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=getchar();return res*fg; } const int N=110005; int h[N],e[2*N],ne[2*N],idx; ll w[2*N]; void add(int a,int b,ll c){e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;}int n,m; struct node1 {int op,u,x;int l,r; }q[N]; struct node2 {int op,id;int t,l,r;ll x; }q0[N<<1]; int dfn[N],timestamp; ll dis[N]; int sz[N]; void dfs(int u,int fa) {dfn[u]=++timestamp;sz[u]=1;for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(v==fa) continue;dis[v]=dis[u]+w[i];dfs(v,u);sz[u]+=sz[v];} } vector<int> V0[N],V1[N]; ll v[N<<2]; ll ans[N]; void modify(int u,int l,int r,int pos,ll x) {if(l==r) return v[u]=x,void();int mid=l+r>>1;if(pos<=mid) modify(u<<1,l,mid,pos,x);else modify(u<<1|1,mid+1,r,pos,x);v[u]=max(v[u<<1],v[u<<1|1]); } ll query(int u,int l,int r,int L,int R) {if(L<=l&&r<=R) return v[u];int mid=l+r>>1;ll c=-1;if(L<=mid) c=max(c,query(u<<1,l,mid,L,R));if(R>mid)c=max(c,query(u<<1|1,mid+1,r,L,R));return c; }struct node3 {int id;ll v;node3(){}node3(int id,ll v):id(id),v(v){}bool operator<(const node3&o)const{return v>o.v||v==o.v&&id<o.id;} }; multiset<node3> mp[N]; multiset<node3>::iterator it; void solve(int l,int r) {if(l>=r) return;int mid=l+r>>1;solve(l,mid),solve(mid+1,r);int i=l;for(int j=mid+1;j<=r;j++){while(i<=mid&&q0[i].t<=q0[j].t){if(q0[i].op==0) {if(q0[i].x<0) {it=mp[q0[i].r].find(node3(q0[i].t-q0[i].l,-q0[i].x));if(it!=mp[q0[i].r].end()) mp[q0[i].r].erase(it);}elsemp[q0[i].r].insert(node3(q0[i].t,q0[i].x));if(mp[q0[i].r].size()) modify(1,1,n,q0[i].r,mp[q0[i].r].begin()->v);elsemodify(1,1,n,q0[i].r,-1);}i++;}if(q0[j].op==1) ans[q0[j].id]=max(ans[q0[j].id],query(1,1,n,q0[j].l,q0[j].r));}while(i>l) {--i;if(q0[i].op==0){modify(1,1,n,q0[i].r,-1);mp[q0[i].r].clear();}}inplace_merge(q0+l,q0+mid+1,q0+r+1,[](const node2&a,const node2&b){return a.t<b.t;}); } int main() {n=rd(),m=rd();memset(h,-1,sizeof h);memset(v,-1,sizeof v);memset(ans,-1,sizeof ans);for(int i=1;i<n;i++) {int u=rd(),v=rd(),c=rd();add(u,v,c),add(v,u,c);}for(int i=1;i<=m;i++){q[i].op=rd();q[i].u=rd();if(q[i].op) {q[i].l=rd(),q[i].r=rd(),q[i].x=rd();V1[q[i].x].push_back(i);}else {q[i].x=rd();V0[q[i].x].push_back(i);}}dis[1]=1;dfs(1,0);int cnt;for(int i=1;i<=n;i++){if(V1[i].empty()) continue;cnt=0;for(int j=i;j<=n;j+=i){for(int k:V0[j]){int u=q[k].u;q0[++cnt]={0,k,dfn[u],j,j,dis[u]};q0[++cnt]={0,k,dfn[u]+sz[u],sz[u],j,-dis[u]};}}for(int k:V1[i]){int u=q[k].u,l=q[k].l,r=q[k].r;q0[++cnt]={1,k,dfn[u],l,r};}sort(q0+1,q0+1+cnt,[](const node2& a,const node2 &b){return a.id<b.id||a.id==b.id&&a.t<b.t;});solve(1,cnt);}for(int i=1;i<=m;i++){if(q[i].op==0) continue;if(ans[i]==-1)puts("Impossible!");elseprintf("%lld\n",dis[q[i].u]-ans[i]);} }

調了一天了，現在感覺這樣寫不太行www，cdq分治必須貢獻能夠分開計算，顯然最大值不能貢獻累加，導致上面寫法可能不太行，草（一種植物）一天沒了~

總結

以上是生活随笔為你收集整理的2021牛客暑期多校训练营3 G-Yu Ling(Ling YueZheng) and Colorful Tree（cdq分治）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。