// this is my noip. #include using namespace std; constexpr int Spp{1<<20}; char buf[Spp],*p1,*p2; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,Spp,stdin),p1==p2)?EOF:*p1++) template void read(T &x) { char c;int f{1}; do x=(c=getchar())-'0'; while (!isdigit(c)&&c!='-'); if (c=='-') x=0,f=-1; while (isdigit(c=getchar())) x=x*10+(c-'0'); x*=f; } template void read(T &x,Args &...args) { read(x);read(args...);} constexpr int N(5e5),LG{18}; vector e[N+5]; int fz[N+5],fa[N+5],dep[N+5],lda,dfn[N+5]; int st[LG+1][N+5]; void init(int u,int fa) { ::fa[u]=fa; dfn[u]=++lda; fz[lda]=u; dep[u]=dep[fa]+1; for (auto v:e[u]) if (v!=fa) init(v,u); } int Max(int u,int v) { return dep[fz[u]]v) swap(u,v); int z{__lg(v-u)}; return fa[fz[Max(st[z][v],st[z][u+(1< ans[N*4],ans2[N*4]; vector> lo[N*4],ro[N*4],oo[N*4],lr[N*4],nl[N*4],nr[N*4]; int LC[N*4]; void build(int p,int L,int R) { ans[p].resize(R-L+2); ans2[p].resize(R-L+2); if (L==R) { ans[p][1]=dep[L]; lo[p].emplace_back(L,L); ro[p].emplace_back(R,R); LC[p]=L; return; } int mid{L+R>>1}; build(p<<1,L,mid); build(p<<1|1,mid+1,R); LC[p]=LCA(LC[p<<1],LC[p<<1|1]); for (int i{1};i<=mid-L+1;++i) ans[p][i]=ans[p<<1][i]; for (int i{1};i<=R-mid;++i) ans[p][i]=max(ans[p][i],ans[p<<1|1][i]); lo[p]=lo[p<<1]; ro[p]=ro[p<<1|1]; for (auto [x,y]:lo[p<<1|1]) nr[p].emplace_back(LCA(x,mid),y),lo[p].emplace_back(LCA(x,LC[p<<1]),y); for (auto [x,y]:ro[p<<1]) nl[p].emplace_back(LCA(x,mid+1),y),ro[p].emplace_back(LCA(x,LC[p<<1|1]),y); merge(nl[p].begin(),nl[p].end(),nr[p].begin(),nr[p].end(),back_inserter(oo[p]),[](auto x,auto y){return dep[x.first]>dep[y.first];}); int l{mid},r{mid+1},an{N}; for (auto [x,y]:oo[p]) { l=min(l,y); r=max(r,y); lr[p].emplace_back(l,r); an=min(an,dep[x]); ans2[p][r-l+1]=max(ans2[p][r-l+1],an); } ans[p][R-L+1]=max(ans[p][R-L+1],ans2[p][R-L+1]); for (int i{R-L};i>=1;--i) ans[p][i]=max({ans[p][i],ans2[p][i],ans[p][i+1]}); lo[p<<1].clear();lo[p<<1].shrink_to_fit(); ro[p<<1|1].clear();ro[p<<1|1].shrink_to_fit(); } int n; int qry(int p,int l,int r,int k,int L,int R) { if (l<=L&&R<=r) return k>(R-L+1)?0:ans[p][k]; int mid{L+R>>1}; int res{0}; if (l<=mid) res=max(res,qry(p<<1,l,r,k,L,mid)); if (r>mid) res=max(res,qry(p<<1|1,l,r,k,mid+1,R)); if (k<=R-L+1&&l<=mid&&r>mid) { if (l<=L) { if (r-k+1>=L) res=max(res,min(ans2[p][k],dep[nl[p][max(0,mid-(r-k+1))].first])); } else if (r>=R) { if (l+k-1<=R) res=max(res,min(ans2[p][k],dep[nr[p][max(0,(l+k-1)-mid-1)].first])); } else { int ll{0},rr{R-L}; int l1{l},l2{r-k+1}; int r2{r},r1{l+k-1}; while (ll<=rr) { int md{ll+rr>>1}; auto [LL,RR]{lr[p][md]}; if (RR-LL+1=r1||LL<=l2&&RR>=r2||LL>=l&&LL+k-1<=r||RR<=r&&RR-k+1>=l) { res=max(res,dep[oo[p][md].first]); rr=md-1; } else ll=md+1; } } } return res; } int main() { // freopen("query.in","r",stdin); // freopen("query.out","w",stdout); read(n); for (int i{1};i

题库

题库

1020.[NOIP2024] 树上查询

题解大全 共 0 篇

测试用例

题解大全共 0 篇