请求开放题解通道
查看原帖
请求开放题解通道
845460
Harmonic_qwq楼主2024/12/3 21:34

理由:题解区里的题解有许多题解是转化为查询

maxlirk{min  tjijk}\underset{l \le i \le r-k}{max} \{ \underset{i \le j \le k}{min\;t_j} \}

来做的,但推到

min{rj,nxti}max{lj,prei}+1kjmin \{ r_j,nxt_i \} - max \{ l_j,pre_i \}+1 \ge k_j

这一步时,还应加上lirl \le i \le r这一条件,否则,对于一个形如preilnxtil+k1i<lpre_i\le l \land nxt_i\ge l+k-1 \land i<lii会对jj产生贡献,但实际上,并不能取到tit_i作为贡献

尽管可以证明去掉它不对答案产生影响,但似乎没有题解证明这一点,建议加入这一篇题解作为补充

2024/12/3 21:34
加载中...