我们考虑先预处理出对于每一个 iii,l=il=il=i 时的最长完美子段长度,设为 gig_igi。
那么对于询问 [l,r][l,r][l,r],考虑二分长度 xxx,那么左端点 p∈[l,r−x+1]p \in [l,r-x+1]p∈[l,r−x+1]。
我们求出 gpg_pgp 最大值,如果大于等于 xxx,则存在 ≥x\geq x≥x 的子段。
预处理可以二分+主席树,询问二分+RMQ,整体下来两只 log\loglog。
口胡的。
By signing up a HFOJ universal account, you can submit code and join discussions in all online judging services provided by us.
Using your HFOJ universal account