NOIP2024T4

NOIP2024T4:
知周所众:

$$LCA^{*}(l,r) = \min_{l \le i \le r - 1} dep_{lca(i,i + 1)}$$

求

$$\max_{l \le l' \le r' \le r,r'-l'+1 \ge k} dep_{LCA^{*}(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')}$$

$$\implies \max_{l \le l' \le r' \le r,r'-l'+1 = k} dep_{LCA^{*}(l',r')}$$

$$\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)})$$

$$\implies \max_{l \le l' \le l' + k - 1 \le r} (\min_{l' \le i \le l' + k - 2} dep_{lca(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)})$$

本人是蒟蒻，推导若有错误请指正