LGP11364 [NOIP 2024] 树上查询 学习笔记
Luogu Link
前言
过了八个月后……
\(\text{Finally, done.}\)
题意简述
给定一棵 \(n\) 个结点、以 \(1\) 为根的树。定义一个结点 \(u\) 的深度为 \(1\to u\) 简单路径上的结点数量。
定义 \(\text{LCA*}(l,r)\) 为编号在 \([l,r]\) 中的所有结点的最近公共祖先。
\(m\) 个询问，每个询问给出 \(l,r,k\)，你需要回答：\(\max_{l\le l'\le r'\le r\land r'-l'+1\ge k}dep_{\text{LCA*}(l',r')}\)。
\(n,m\le 5\times 10^5\)。对于每个询问保证 \(r'-l'+1\ge k\)。虽然两 \(\log\) 有不小机会干过去，但那设计上只有 \(\text{80pts}\)。为了达到训练效果，请写单 \(\log\) 做法。
做法解析
首先这个问题需要一个转化。
问题转化完毕。有 \(O(n)\) 个形如 \([sl,sr]\)，权值为 \(v\) 的线段，\(m\) 次询问，每次给定 \([ql,qr,k]\)，问与区间 \([ql,qr]\) 交集至少为 \(k\) 的线段中最大的权值。
首先显然可以三维偏序来做，此不赘述。现在你有 \(\text{80pts}\) 了。但是我们来思考优美的单 \(\log\)。
想要单 \(\log\) 需要偏序关系降到二维。怎么降呢？答案是分类讨论。
对于 \(sl\le ql\le qr\le sr\) 的，我们不需要考虑 \(k\) 这一维的偏序，因为题目保证了 \(qr-ql+1\ge k\)，所以也必然有 \(sr-sl+1\ge k\)。这里就是直接二维偏序就行。
对于 \(ql\le sl\le qr\le sr\) 或 \(sl\le ql\le sr\le qr\) 的，我们去扫描 \(k\) 这一维，这个想法较为重要，值得学习：
- 一方面我们发现这两个问题有对称性，而 \(k\) 是它们都免不掉要扫的一维。
- 另一方面因为我们需要降维，我们必须就要松掉一维度的限制。我们对于 \(ql\le sl\le qr\le sr\) 松掉 \(qr\le sr\) 这一维，对于 \(sl\le ql\le sr\le qr\) 松掉 \(sl\le ql\) 这一维。这样我们既降了维，又允许出现 \(ql\le sl\le sr\le qr\) 的情况，顺便就把它统计上了。
这时如果你饭堂了，可能会问出这样一个问题：
那 \(ql\le sl\le sr\le qr\) 的情况不是明晃晃算重了吗？
的确，这种情况被考虑了两遍，但我们在做的是更新最大值而并不是加和，所以最大值你重复扫对答案正确性没有影响。
推而广之来讲，求最大值的时候，你更新失败是在 maxxer(ans,0)，就对答案正确性没有影响。
代码实现
纯板，代码没有任何好讲的。
#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=5e5+5;
int N,M,X,Y,Z,ans[MaxN];
vector<int> Tr[MaxN];
void addudge(int u,int v){Tr[u].push_back(v);Tr[v].push_back(u);
}
int tfa[MaxN],dep[MaxN],siz[MaxN],hvs[MaxN];
void dfs1(int u,int f){dep[u]=dep[f]+1,tfa[u]=f,siz[u]=1;for(int v : Tr[u]){if(v==f)continue;dfs1(v,u),siz[u]+=siz[v];if(siz[v]>siz[hvs[u]])hvs[u]=v;}
}
int dfn[MaxN],dcnt,top[MaxN];
void dfs2(int u,int t){dfn[u]=++dcnt,top[u]=t;if(hvs[u])dfs2(hvs[u],t);for(int v : Tr[u])if(v!=tfa[u]&&v!=hvs[u])dfs2(v,v);
}
int getlca(int x,int y){while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y);x=tfa[top[x]];}return dep[x]<=dep[y]?x:y;
}
struct SegTree{int mx[MaxN<<2];int ls(int u){return u<<1;}int rs(int u){return (u<<1)|1;}void pushup(int u){mx[u]=max(mx[ls(u)],mx[rs(u)]);}void update(int u,int cl,int cr,int dd,int x){if(cl==cr){maxxer(mx[u],x);return;}int cmid=(cl+cr)>>1;dd<=cmid?update(ls(u),cl,cmid,dd,x):update(rs(u),cmid+1,cr,dd,x);pushup(u);}int getmax(int u,int cl,int cr,int dl,int dr){if(dl<=cl&&cr<=dr)return mx[u];int cmid=(cl+cr)>>1,res=0;if(dl<=cmid)maxxer(res,getmax(ls(u),cl,cmid,dl,dr));if(dr>cmid)maxxer(res,getmax(rs(u),cmid+1,cr,dl,dr));return res;}
}SgT[3];
int A[MaxN],H[MaxN],stk[MaxN],ktp;
int sls[MaxN],srs[MaxN];
struct anob{int l,r,x;}S[MaxN];
vector<pii> G2[MaxN],Q2[MaxN];
vector<anob> G1[MaxN],Q1[MaxN];
void dfs3(int u,int l,int r){S[u]={l,r,H[u]};if(sls[u])dfs3(sls[u],l,u);if(srs[u])dfs3(srs[u],u+1,r);
}
int main(){readi(N);for(int i=1;i<N;i++)readis(X,Y),addudge(X,Y);dfs1(1,0),dfs2(1,1);for(int i=1;i<N;i++)A[i]=getlca(i,i+1),H[i]=dep[A[i]];for(int i=1,k;i<N;i++,ktp=k){for(k=ktp;H[stk[k]]>H[i];k--);if(k<ktp)sls[i]=stk[k+1];srs[stk[k]]=i,stk[++k]=i;}dfs3(stk[1],1,N);readi(M);for(int i=1;i<=M;i++){readis(X,Y,Z);Q1[Z].push_back({X,Y,i});Q2[X].push_back({Y,i});}for(int i=1;i<N;i++){auto [l,r,h]=S[i];G1[r-l+1].push_back(S[i]);}for(int i=1;i<=N;i++)G1[1].push_back({i,i,dep[i]});for(int k=N;k>=1;k--){for(auto [l,r,h] : G1[k]){SgT[0].update(1,1,N,l,h);SgT[1].update(1,1,N,r,h);}for(auto [l,r,id] : Q1[k]){maxxer(ans[id],SgT[0].getmax(1,1,N,l,r-k+1));maxxer(ans[id],SgT[1].getmax(1,1,N,l+k-1,r));}}for(int i=1;i<N;i++){auto [l,r,h]=S[i];G2[l].push_back({r,h});}for(int i=1;i<=N;i++){for(auto [r,h] : G2[i])SgT[2].update(1,1,N,r,h);for(auto [r,id] : Q2[i])maxxer(ans[id],SgT[2].getmax(1,1,N,r,N));}for(int i=1;i<=M;i++)writil(ans[i]);return 0;
}