1 solutions

  • 0
    @ 2026-10-6 16:39:35

    来个无脑点的做法,考虑分块。每个块维护 li,ri,fil_i,r_i,f_i 表示 ii 在块中第一次出现的位置和最后一次出现的位置,还有块内包含 ii 的连续段长度的最大值,每个点再维护 Li,RiL_i,R_i 表示 ii 往左往右在相同块内的连续段长度,每次修改就直接重构整个块即可。

    考虑一次询问,只会出现 O(n)\mathcal O(\sqrt n) 个跨越两个块的连续段,直接从前往后扫每个块,利用上面维护的那些东西不难求出所有跨越多个块的连续段的长度与是否含有 xx,只在一个块内的答案就是 fxf_x,散块就直接暴力加入即可。时间复杂度 O(nn)\mathcal O(n\sqrt n),有点卡常。

    • 1

    Information

    ID
    32
    Time
    3000ms
    Memory
    512MiB
    Difficulty
    10
    Tags
    (None)
    # Submissions
    28
    Accepted
    1
    Uploaded By