NOIP2024T4:
知周所众:
LCA∗(l,r)=minl≤i≤r−1deplca(i,i+1)LCA^{*}(l,r) = \min_{l \le i \le r - 1} dep_{lca(i,i + 1)} LCA∗(l,r)=l≤i≤r−1min deplca(i,i+1)
求
maxl≤l′≤r′≤r,r′−l′+1≥kdepLCA∗(l′,r′)\max_{l \le l' \le r' \le r,r'-l'+1 \ge k} dep_{LCA^{*}(l',r')} l≤l′≤r′≤r,r′−l′+1≥kmax depLCA∗(l′,r′)
知周所众:
maxl≤l′≤r′≤r,r′−l′+1≥kdepLCA∗(l′,r′)≤maxl≤l′≤r′≤r,r′−l′+1=kdepLCA∗(l′,r′)\max_{l \le l' \le r' \le r,r'-l'+1 \ge k} dep_{LCA^{*}(l',r')} \le \max_{l \le l' \le r' \le r,r'-l'+1 = k} dep_{LCA^{*}(l',r')} l≤l′≤r′≤r,r′−l′+1≥kmax depLCA∗(l′,r′) ≤l≤l′≤r′≤r,r′−l′+1=kmax depLCA∗(l′,r′)
⟹ maxl≤l′≤r′≤r,r′−l′+1=kdepLCA∗(l′,r′)\implies \max_{l \le l' \le r' \le r,r'-l'+1 = k} dep_{LCA^{*}(l',r')} ⟹l≤l′≤r′≤r,r′−l′+1=kmax depLCA∗(l′,r′)
⟹ maxl≤l′≤r′≤r,r′−l′+1=k(minl′≤i≤r′−1deplca(i,i+1))\implies \max_{l \le l' \le r' \le r,r'-l'+1 = k} (\min_{l' \le i \le r' - 1} dep_{lca(i,i + 1)}) ⟹l≤l′≤r′≤r,r′−l′+1=kmax (l′≤i≤r′−1min deplca(i,i+1) )
⟹ maxl≤l′≤l′+k−1≤r(minl′≤i≤l′+k−2deplca(i,i+1))\implies \max_{l \le l' \le l' + k - 1 \le r} (\min_{l' \le i \le l' + k - 2} dep_{lca(i,i + 1)}) ⟹l≤l′≤l′+k−1≤rmax (l′≤i≤l′+k−2min deplca(i,i+1) )
综上得到答案表达式:
ans=maxl≤l′≤l′+k−1≤r(minl′≤i≤l′+k−2deplca(i,i+1))ans = \max_{l \le l' \le l' + k - 1 \le r} (\min_{l' \le i \le l' + k - 2} dep_{lca(i,i + 1)}) ans=l≤l′≤l′+k−1≤rmax (l′≤i≤l′+k−2min deplca(i,i+1) )
本人是蒟蒻，推导若有错误请指正
